<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xml:lang="en" lang="en">
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>Structure and Interpretation of Computer Programs, 2e: 4.4</title>

<meta name="description" content="Structure and Interpretation of Computer Programs, 2e: 4.4" />
<meta name="keywords" content="Structure and Interpretation of Computer Programs, 2e: 4.4" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="Generator" content="texi2any" />
<meta charset="utf-8" />
<link href="index.xhtml#Top" rel="start" title="Top" />
<link href="Term-Index.xhtml#Term-Index" rel="index" title="Term Index" />
<link href="index.xhtml#SEC_Contents" rel="contents" title="Table of Contents" />
<link href="Chapter-4.xhtml#Chapter-4" rel="prev" title="Chapter 4" />
<link href="Chapter-5.xhtml#Chapter-5" rel="next" title="Chapter 5" />
<link href="4_002e3.xhtml#g_t4_002e3_002e3" rel="prev" title="4.3.3" />

<link href="css/style.css" rel="stylesheet" type="text/css" />
<link href="css/prettify.css" rel="stylesheet" type="text/css" />
</head>

<body>
<section><span class="top jump" title="Jump to top"><a href="#pagetop" accesskey="t">⇡</a></span><a id="pagetop"></a><a id="g_t4_002e4"></a>
<nav class="header">
<p>
Next: <a href="Chapter-5.xhtml#Chapter-5" accesskey="n" rel="next">Chapter 5</a>, Prev: <a href="4_002e3.xhtml#g_t4_002e3" accesskey="p" rel="prev">4.3</a>, Up: <a href="Chapter-4.xhtml#Chapter-4" accesskey="u" rel="prev">Chapter 4</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>
<a id="Logic-Programming"></a>
<h3 class="section"><span class="secnum">4.4</span><span class="sectitle">Logic Programming</span></h3>

<p>In <a href="Chapter-1.xhtml#Chapter-1">Chapter 1</a> we stressed that computer science deals with imperative (how
to) knowledge, whereas mathematics deals with declarative (what is) knowledge.
Indeed, programming languages require that the programmer express knowledge in
a form that indicates the step-by-step methods for solving particular problems.
On the other hand, high-level languages provide, as part of the language
implementation, a substantial amount of methodological knowledge that frees the
user from concern with numerous details of how a specified computation will
progress.
</p>
<p>Most programming languages, including Lisp, are organized around computing the
values of mathematical functions.  Expression-oriented languages (such as Lisp,
Fortran, and Algol) capitalize on the “pun” that an expression that describes
the value of a function may also be interpreted as a means of computing that
value.  Because of this, most programming languages are strongly biased toward
unidirectional computations (computations with well-defined inputs and
outputs).  There are, however, radically different programming languages that
relax this bias.  We saw one such example in <a href="3_002e3.xhtml#g_t3_002e3_002e5">3.3.5</a>, where the
objects of computation were arithmetic constraints.  In a constraint system the
direction and the order of computation are not so well specified; in carrying
out a computation the system must therefore provide more detailed “how to”
knowledge than would be the case with an ordinary arithmetic computation.  This
does not mean, however, that the user is released altogether from the
responsibility of providing imperative knowledge.  There are many constraint
networks that implement the same set of constraints, and the user must choose
from the set of mathematically equivalent networks a suitable network to
specify a particular computation.
</p>
<p>The nondeterministic program evaluator of <a href="4_002e3.xhtml#g_t4_002e3">4.3</a> also moves away
from the view that programming is about constructing algorithms for computing
unidirectional functions.  In a nondeterministic language, expressions can have
more than one value, and, as a result, the computation is dealing with
relations rather than with single-valued functions.  Logic programming extends
this idea by combining a relational vision of programming with a powerful kind
of symbolic pattern matching called <a id="index-unification"></a>
<em>unification</em>.<a class="footnote_link" id="DOCF262" href="#FOOT262"><sup>262</sup></a>
</p>
<p>This approach, when it works, can be a very powerful way to write programs.
Part of the power comes from the fact that a single “what is” fact can be
used to solve a number of different problems that would have different “how
to” components.  As an example, consider the <code>append</code> operation, which
takes two lists as arguments and combines their elements to form a single list.
In a procedural language such as Lisp, we could define <code>append</code> in terms
of the basic list constructor <code>cons</code>, as we did in <a href="2_002e2.xhtml#g_t2_002e2_002e1">2.2.1</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">append x y</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? x</span><span class="clo">)</span><span class="pln"> 
      y 
      </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">append </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> x</span><span class="clo">)</span><span class="pln"> y</span><span class="clo">))))</span></pre></div>

<p>This procedure can be regarded as a translation into Lisp of the following two
rules, the first of which covers the case where the first list is empty and the
second of which handles the case of a nonempty list, which is a <code>cons</code> of
two parts:
</p>
<ul>
<li> For any list <code>y</code>, the empty list and <code>y</code> <code>append</code> to form
<code>y</code>.

</li><li> For any <code>u</code>, <code>v</code>, <code>y</code>, and <code>z</code>, <code>(cons u v)</code> and
<code>y</code> <code>append</code> to form <code>(cons u z)</code> if <code>v</code> and <code>y</code>
<code>append</code> to form <code>z</code>.<a class="footnote_link" id="DOCF263" href="#FOOT263"><sup>263</sup></a>

</li></ul>

<p>Using the <code>append</code> procedure, we can answer questions such as
</p>
<blockquote>
<p>Find the <code>append</code> of <code>(a b)</code> and <code>(c d)</code>.
</p></blockquote>

<p>But the same two rules are also sufficient for answering the following sorts of
questions, which the procedure can’t answer:
</p>
<blockquote>
<p>Find a list <code>y</code> that <code>append</code>s with <code>(a b)</code> to produce <code>(a
b c d)</code>.
</p>
<p>Find all <code>x</code> and <code>y</code> that <code>append</code> to form <code>(a b c d)</code>.
</p></blockquote>

<p>In a logic programming language, the programmer writes an <code>append</code>
“procedure” by stating the two rules about <code>append</code> given above.  “How
to” knowledge is provided automatically by the interpreter to allow this
single pair of rules to be used to answer all three types of questions about
<code>append</code>.<a class="footnote_link" id="DOCF264" href="#FOOT264"><sup>264</sup></a>
</p>
<p>Contemporary logic programming languages (including the one we implement here)
have substantial deficiencies, in that their general “how to” methods can
lead them into spurious infinite loops or other undesirable behavior.  Logic
programming is an active field of research in computer
science.<a class="footnote_link" id="DOCF265" href="#FOOT265"><sup>265</sup></a>
</p>
<p>Earlier in this chapter we explored the technology of implementing interpreters
and described the elements that are essential to an interpreter for a Lisp-like
language (indeed, to an interpreter for any conventional language).  Now we
will apply these ideas to discuss an interpreter for a logic programming
language.  We call this language the <a id="index-query-language"></a>
<em>query language</em>, because it is
very useful for retrieving information from data bases by formulating
<a id="index-queries"></a>
<em>queries</em>, or questions, expressed in the language.  Even though the
query language is very different from Lisp, we will find it convenient to
describe the language in terms of the same general framework we have been using
all along: as a collection of primitive elements, together with means of
combination that enable us to combine simple elements to create more complex
elements and means of abstraction that enable us to regard complex elements as
single conceptual units.  An interpreter for a logic programming language is
considerably more complex than an interpreter for a language like Lisp.
Nevertheless, we will see that our query-language interpreter contains many of
the same elements found in the interpreter of <a href="4_002e1.xhtml#g_t4_002e1">4.1</a>.  In
particular, there will be an “eval” part that classifies expressions
according to type and an “apply” part that implements the language’s
abstraction mechanism (procedures in the case of Lisp, and <a id="index-rules"></a>
<em>rules</em> in
the case of logic programming).  Also, a central role is played in the
implementation by a frame data structure, which determines the correspondence
between symbols and their associated values.  One additional interesting aspect
of our query-language implementation is that we make substantial use of
streams, which were introduced in <a href="Chapter-3.xhtml#Chapter-3">Chapter 3</a>.
</p>

<a id="g_t4_002e4_002e1"></a>
<a id="Deductive-Information-Retrieval"></a>
<h4 class="subsection"><span class="secnum">4.4.1</span><span class="sectitle">Deductive Information Retrieval</span></h4>

<p>Logic programming excels in providing interfaces to data bases for information
retrieval.  The query language we shall implement in this chapter is designed
to be used in this way.
</p>
<p>In order to illustrate what the query system does, we will show how it can be
used to manage the data base of personnel records for Microshaft, a thriving
high-technology company in the Boston area.  The language provides
pattern-directed access to personnel information and can also take advantage of
general rules in order to make logical deductions.
</p>
<a id="A-sample-data-base"></a>
<h5 class="subsubheading">A sample data base</h5>

<p>The personnel data base for Microshaft contains <a id="index-assertions"></a>
<em>assertions</em> about
company personnel.  Here is the information about Ben Bitdiddle, the resident
computer wizard:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">address </span><span class="opn">(</span><span class="pln">Bitdiddle Ben</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">Slumerville </span><span class="opn">(</span><span class="pln">Ridge Road</span><span class="clo">)</span><span class="pln"> </span><span class="lit">10</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">job </span><span class="opn">(</span><span class="pln">Bitdiddle Ben</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">computer wizard</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">salary </span><span class="opn">(</span><span class="pln">Bitdiddle Ben</span><span class="clo">)</span><span class="pln"> </span><span class="lit">60000</span><span class="clo">)</span></pre></div>

<p>Each assertion is a list (in this case a triple) whose elements can themselves
be lists.
</p>
<p>As resident wizard, Ben is in charge of the company’s computer division, and he
supervises two programmers and one technician.  Here is the information about
them:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">address </span><span class="opn">(</span><span class="pln">Hacker Alyssa P</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">Cambridge </span><span class="opn">(</span><span class="pln">Mass Ave</span><span class="clo">)</span><span class="pln"> </span><span class="lit">78</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">job </span><span class="opn">(</span><span class="pln">Hacker Alyssa P</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">computer programmer</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">salary </span><span class="opn">(</span><span class="pln">Hacker Alyssa P</span><span class="clo">)</span><span class="pln"> </span><span class="lit">40000</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">supervisor </span><span class="opn">(</span><span class="pln">Hacker Alyssa P</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">Bitdiddle Ben</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">address </span><span class="opn">(</span><span class="pln">Fect Cy D</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">Cambridge </span><span class="opn">(</span><span class="pln">Ames Street</span><span class="clo">)</span><span class="pln"> </span><span class="lit">3</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">job </span><span class="opn">(</span><span class="pln">Fect Cy D</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">computer programmer</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">salary </span><span class="opn">(</span><span class="pln">Fect Cy D</span><span class="clo">)</span><span class="pln"> </span><span class="lit">35000</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">supervisor </span><span class="opn">(</span><span class="pln">Fect Cy D</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">Bitdiddle Ben</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">address </span><span class="opn">(</span><span class="pln">Tweakit Lem E</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">Boston </span><span class="opn">(</span><span class="pln">Bay State Road</span><span class="clo">)</span><span class="pln"> </span><span class="lit">22</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">job </span><span class="opn">(</span><span class="pln">Tweakit Lem E</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">computer technician</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">salary </span><span class="opn">(</span><span class="pln">Tweakit Lem E</span><span class="clo">)</span><span class="pln"> </span><span class="lit">25000</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">supervisor </span><span class="opn">(</span><span class="pln">Tweakit Lem E</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">Bitdiddle Ben</span><span class="clo">))</span></pre></div>

<p>There is also a programmer trainee, who is supervised by Alyssa:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">address </span><span class="opn">(</span><span class="pln">Reasoner Louis</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">Slumerville </span><span class="opn">(</span><span class="pln">Pine Tree Road</span><span class="clo">)</span><span class="pln"> </span><span class="lit">80</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">job </span><span class="opn">(</span><span class="pln">Reasoner Louis</span><span class="clo">)</span><span class="pln"> 
     </span><span class="opn">(</span><span class="pln">computer programmer trainee</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">salary </span><span class="opn">(</span><span class="pln">Reasoner Louis</span><span class="clo">)</span><span class="pln"> </span><span class="lit">30000</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">supervisor </span><span class="opn">(</span><span class="pln">Reasoner Louis</span><span class="clo">)</span><span class="pln"> 
            </span><span class="opn">(</span><span class="pln">Hacker Alyssa P</span><span class="clo">))</span></pre></div>

<p>All of these people are in the computer division, as indicated by the word
<code>computer</code> as the first item in their job descriptions.
</p>
<p>Ben is a high-level employee.  His supervisor is the company’s big wheel
himself:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">supervisor </span><span class="opn">(</span><span class="pln">Bitdiddle Ben</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">Warbucks Oliver</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">address </span><span class="opn">(</span><span class="pln">Warbucks Oliver</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">Swellesley </span><span class="opn">(</span><span class="pln">Top Heap Road</span><span class="clo">)))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">job </span><span class="opn">(</span><span class="pln">Warbucks Oliver</span><span class="clo">)</span><span class="pln"> 
     </span><span class="opn">(</span><span class="pln">administration big wheel</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">salary </span><span class="opn">(</span><span class="pln">Warbucks Oliver</span><span class="clo">)</span><span class="pln"> </span><span class="lit">150000</span><span class="clo">)</span></pre></div>

<p>Besides the computer division supervised by Ben, the company has an accounting
division, consisting of a chief accountant and his assistant:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">address </span><span class="opn">(</span><span class="pln">Scrooge Eben</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">Weston </span><span class="opn">(</span><span class="pln">Shady Lane</span><span class="clo">)</span><span class="pln"> </span><span class="lit">10</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">job </span><span class="opn">(</span><span class="pln">Scrooge Eben</span><span class="clo">)</span><span class="pln"> 
     </span><span class="opn">(</span><span class="pln">accounting chief accountant</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">salary </span><span class="opn">(</span><span class="pln">Scrooge Eben</span><span class="clo">)</span><span class="pln"> </span><span class="lit">75000</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">supervisor </span><span class="opn">(</span><span class="pln">Scrooge Eben</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">Warbucks Oliver</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">address </span><span class="opn">(</span><span class="pln">Cratchet Robert</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">Allston </span><span class="opn">(</span><span class="pln">N Harvard Street</span><span class="clo">)</span><span class="pln"> </span><span class="lit">16</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">job </span><span class="opn">(</span><span class="pln">Cratchet Robert</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">accounting scrivener</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">salary </span><span class="opn">(</span><span class="pln">Cratchet Robert</span><span class="clo">)</span><span class="pln"> </span><span class="lit">18000</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">supervisor </span><span class="opn">(</span><span class="pln">Cratchet Robert</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">Scrooge Eben</span><span class="clo">))</span></pre></div>

<p>There is also a secretary for the big wheel:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">address </span><span class="opn">(</span><span class="pln">Aull DeWitt</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">Slumerville </span><span class="opn">(</span><span class="pln">Onion Square</span><span class="clo">)</span><span class="pln"> </span><span class="lit">5</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">job </span><span class="opn">(</span><span class="pln">Aull DeWitt</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">administration secretary</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">salary </span><span class="opn">(</span><span class="pln">Aull DeWitt</span><span class="clo">)</span><span class="pln"> </span><span class="lit">25000</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">supervisor </span><span class="opn">(</span><span class="pln">Aull DeWitt</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">Warbucks Oliver</span><span class="clo">))</span></pre></div>

<p>The data base also contains assertions about which kinds of jobs can be done by
people holding other kinds of jobs.  For instance, a computer wizard can do the
jobs of both a computer programmer and a computer technician:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">can-do-job </span><span class="opn">(</span><span class="pln">computer wizard</span><span class="clo">)</span><span class="pln"> 
            </span><span class="opn">(</span><span class="pln">computer programmer</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">can-do-job </span><span class="opn">(</span><span class="pln">computer wizard</span><span class="clo">)</span><span class="pln"> 
            </span><span class="opn">(</span><span class="pln">computer technician</span><span class="clo">))</span></pre></div>

<p>A computer programmer could fill in for a trainee:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">can-do-job </span><span class="opn">(</span><span class="pln">computer programmer</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">computer programmer trainee</span><span class="clo">))</span></pre></div>

<p>Also, as is well known,
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">can-do-job </span><span class="opn">(</span><span class="pln">administration secretary</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">administration big wheel</span><span class="clo">))</span></pre></div>

<a id="Simple-queries"></a>
<h5 class="subsubheading">Simple queries</h5>

<p>The query language allows users to retrieve information from the data base by
posing queries in response to the system’s prompt.  For example, to find all
computer programmers one can say
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><i><span class="com">;;; Query input:</span></i><span class="pln">
</span><span class="opn">(</span><span class="pln">job </span><span class="pun">?</span><span class="pln">x </span><span class="opn">(</span><span class="pln">computer programmer</span><span class="clo">))</span></pre></div>

<p>The system will respond with the following items:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><i><span class="com">;;; Query results:</span></i><span class="pln">
</span><span class="opn">(</span><span class="pln">job </span><span class="opn">(</span><span class="pln">Hacker Alyssa P</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">computer programmer</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">job </span><span class="opn">(</span><span class="pln">Fect Cy D</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">computer programmer</span><span class="clo">))</span></pre></div>

<p>The input query specifies that we are looking for entries in the data base that
match a certain <a id="index-pattern"></a>
<em>pattern</em>.  In this example, the pattern specifies
entries consisting of three items, of which the first is the literal symbol
<code>job</code>, the second can be anything, and the third is the literal list
<code>(computer programmer)</code>.  The “anything” that can be the second item in
the matching list is specified by a <a id="index-pattern-variable"></a>
<em>pattern variable</em>, <code>?x</code>.  The
general form of a pattern variable is a symbol, taken to be the name of the
variable, preceded by a question mark.  We will see below why it is useful to
specify names for pattern variables rather than just putting <code>?</code> into
patterns to represent “anything.”  The system responds to a simple query by
showing all entries in the data base that match the specified pattern.
</p>
<p>A pattern can have more than one variable.  For example, the query
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">address </span><span class="pun">?</span><span class="pln">x </span><span class="pun">?</span><span class="pln">y</span><span class="clo">)</span></pre></div>

<p>will list all the employees’ addresses.
</p>
<p>A pattern can have no variables, in which case the query simply determines
whether that pattern is an entry in the data base.  If so, there will be one
match; if not, there will be no matches.
</p>
<p>The same pattern variable can appear more than once in a query, specifying that
the same “anything” must appear in each position.  This is why variables have
names.  For example,
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">supervisor </span><span class="pun">?</span><span class="pln">x </span><span class="pun">?</span><span class="pln">x</span><span class="clo">)</span></pre></div>

<p>finds all people who supervise themselves (though there are no such assertions
in our sample data base).
</p>
<p>The query
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">job </span><span class="pun">?</span><span class="pln">x </span><span class="opn">(</span><span class="pln">computer </span><span class="pun">?</span><span class="pln">type</span><span class="clo">))</span></pre></div>

<p>matches all job entries whose third item is a two-element list whose first item
is <code>computer</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">job </span><span class="opn">(</span><span class="pln">Bitdiddle Ben</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">computer wizard</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">job </span><span class="opn">(</span><span class="pln">Hacker Alyssa P</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">computer programmer</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">job </span><span class="opn">(</span><span class="pln">Fect Cy D</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">computer programmer</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">job </span><span class="opn">(</span><span class="pln">Tweakit Lem E</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">computer technician</span><span class="clo">))</span></pre></div>

<p>This same pattern does <em>not</em> match
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">job </span><span class="opn">(</span><span class="pln">Reasoner Louis</span><span class="clo">)</span><span class="pln"> 
     </span><span class="opn">(</span><span class="pln">computer programmer trainee</span><span class="clo">))</span></pre></div>

<p>because the third item in the entry is a list of three elements, and the
pattern’s third item specifies that there should be two elements.  If we wanted
to change the pattern so that the third item could be any list beginning with
<code>computer</code>, we could specify<a class="footnote_link" id="DOCF266" href="#FOOT266"><sup>266</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">job </span><span class="pun">?</span><span class="pln">x </span><span class="opn">(</span><span class="pln">computer </span><span class="pun">.</span><span class="pln"> </span><span class="pun">?</span><span class="pln">type</span><span class="clo">))</span></pre></div>

<p>For example,
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">computer </span><span class="pun">.</span><span class="pln"> </span><span class="pun">?</span><span class="pln">type</span><span class="clo">)</span></pre></div>

<p>matches the data
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">computer programmer trainee</span><span class="clo">)</span></pre></div>

<p>with <code>?type</code> as the list <code>(programmer trainee)</code>.  It also
matches the data
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">computer programmer</span><span class="clo">)</span></pre></div>

<p>with <code>?type</code> as the list <code>(programmer)</code>, and matches the data
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">computer</span><span class="clo">)</span></pre></div>

<p>with <code>?type</code> as the empty list <code>()</code>.
</p>
<p>We can describe the query language’s processing of simple queries as follows:
</p>
<ul>
<li> The system finds all assignments to variables in the query pattern that
<a id="index-satisfy"></a>
<em>satisfy</em> the pattern—that is, all sets of values for the variables
such that if the pattern variables are <a id="index-instantiated-with"></a>
<em>instantiated with</em> (replaced
by) the values, the result is in the data base.

</li><li> The system responds to the query by listing all instantiations of the query
pattern with the variable assignments that satisfy it.

</li></ul>

<p>Note that if the pattern has no variables, the query reduces to a determination
of whether that pattern is in the data base.  If so, the empty assignment,
which assigns no values to variables, satisfies that pattern for that data
base.
</p>
<blockquote>
<p><strong><a id="Exercise-4_002e55"></a>Exercise 4.55:</strong> Give simple queries that retrieve
the following information from the data base:
</p>
<ol>
<li> all people supervised by Ben Bitdiddle;

</li><li> the names and jobs of all people in the accounting division;

</li><li> the names and addresses of all people who live in Slumerville.

</li></ol>
</blockquote>

<a id="Compound-queries"></a>
<h5 class="subsubheading">Compound queries</h5>

<p>Simple queries form the primitive operations of the query language.  In order
to form compound operations, the query language provides means of combination.
One thing that makes the query language a logic programming language is that
the means of combination mirror the means of combination used in forming
logical expressions: <code>and</code>, <code>or</code>, and <code>not</code>.  (Here <code>and</code>,
<code>or</code>, and <code>not</code> are not the Lisp primitives, but rather operations
built into the query language.)
</p>
<p>We can use <code>and</code> as follows to find the addresses of all the computer
programmers:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">job </span><span class="pun">?</span><span class="pln">person </span><span class="opn">(</span><span class="pln">computer programmer</span><span class="clo">))</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">address </span><span class="pun">?</span><span class="pln">person </span><span class="pun">?</span><span class="pln">where</span><span class="clo">))</span></pre></div>

<p>The resulting output is
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">job </span><span class="opn">(</span><span class="pln">Hacker Alyssa P</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">computer programmer</span><span class="clo">))</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">address </span><span class="opn">(</span><span class="pln">Hacker Alyssa P</span><span class="clo">)</span><span class="pln"> 
              </span><span class="opn">(</span><span class="pln">Cambridge </span><span class="opn">(</span><span class="pln">Mass Ave</span><span class="clo">)</span><span class="pln"> </span><span class="lit">78</span><span class="clo">)))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">job </span><span class="opn">(</span><span class="pln">Fect Cy D</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">computer programmer</span><span class="clo">))</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">address </span><span class="opn">(</span><span class="pln">Fect Cy D</span><span class="clo">)</span><span class="pln"> 
              </span><span class="opn">(</span><span class="pln">Cambridge </span><span class="opn">(</span><span class="pln">Ames Street</span><span class="clo">)</span><span class="pln"> </span><span class="lit">3</span><span class="clo">)))</span></pre></div>

<p>In general,
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">and</span><span class="pln"> ⟨</span><var><span class="pln">query</span><span class="pun">₁</span></var><span class="pln">⟩ ⟨</span><var><span class="pln">query</span><span class="pun">₂</span></var><span class="pln">⟩ </span><span class="roman"><span class="pun">…</span></span><span class="pln"> ⟨</span><var><span class="pln">query</span><span class="pun">ₙ</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>is satisfied by all sets of values for the pattern variables that
simultaneously satisfy <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">⟨</mo>
    <mspace width="0.1em"/>
    <mi>q</mi>
    <mi>u</mi>
    <mi>e</mi>
    <mi>r</mi>
    <msub>
      <mi>y</mi>
      <mn>1</mn>
    </msub>
    <mo stretchy="false">⟩</mo>
  </mrow>
</math> <span class="roman">…</span> <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">⟨</mo>
    <mspace width="0.1em"/>
    <mi>q</mi>
    <mi>u</mi>
    <mi>e</mi>
    <mi>r</mi>
    <msub>
      <mi>y</mi>
      <mi>n</mi>
    </msub>
    <mo stretchy="false">⟩</mo>
  </mrow>
</math>.
</p>
<p>As for simple queries, the system processes a compound query by finding all
assignments to the pattern variables that satisfy the query, then displaying
instantiations of the query with those values.
</p>
<p>Another means of constructing compound queries is through <code>or</code>.  For
example,
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">or</span><span class="pln"> </span><span class="opn">(</span><span class="pln">supervisor </span><span class="pun">?</span><span class="pln">x </span><span class="opn">(</span><span class="pln">Bitdiddle Ben</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">supervisor </span><span class="pun">?</span><span class="pln">x </span><span class="opn">(</span><span class="pln">Hacker Alyssa P</span><span class="clo">)))</span></pre></div>

<p>will find all employees supervised by Ben Bitdiddle or Alyssa P.  Hacker:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">or</span><span class="pln"> </span><span class="opn">(</span><span class="pln">supervisor </span><span class="opn">(</span><span class="pln">Hacker Alyssa P</span><span class="clo">)</span><span class="pln"> 
                </span><span class="opn">(</span><span class="pln">Bitdiddle Ben</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">supervisor </span><span class="opn">(</span><span class="pln">Hacker Alyssa P</span><span class="clo">)</span><span class="pln"> 
                </span><span class="opn">(</span><span class="pln">Hacker Alyssa P</span><span class="clo">)))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">or</span><span class="pln"> </span><span class="opn">(</span><span class="pln">supervisor </span><span class="opn">(</span><span class="pln">Fect Cy D</span><span class="clo">)</span><span class="pln"> 
                </span><span class="opn">(</span><span class="pln">Bitdiddle Ben</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">supervisor </span><span class="opn">(</span><span class="pln">Fect Cy D</span><span class="clo">)</span><span class="pln"> 
                </span><span class="opn">(</span><span class="pln">Hacker Alyssa P</span><span class="clo">)))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">or</span><span class="pln"> </span><span class="opn">(</span><span class="pln">supervisor </span><span class="opn">(</span><span class="pln">Tweakit Lem E</span><span class="clo">)</span><span class="pln"> 
                </span><span class="opn">(</span><span class="pln">Bitdiddle Ben</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">supervisor </span><span class="opn">(</span><span class="pln">Tweakit Lem E</span><span class="clo">)</span><span class="pln"> 
                </span><span class="opn">(</span><span class="pln">Hacker Alyssa P</span><span class="clo">)))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">or</span><span class="pln"> </span><span class="opn">(</span><span class="pln">supervisor </span><span class="opn">(</span><span class="pln">Reasoner Louis</span><span class="clo">)</span><span class="pln"> 
                </span><span class="opn">(</span><span class="pln">Bitdiddle Ben</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">supervisor </span><span class="opn">(</span><span class="pln">Reasoner Louis</span><span class="clo">)</span><span class="pln"> 
                </span><span class="opn">(</span><span class="pln">Hacker Alyssa P</span><span class="clo">)))</span></pre></div>

<p>In general,
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">or</span><span class="pln"> ⟨</span><var><span class="pln">query</span><span class="pun">₁</span></var><span class="pln">⟩ ⟨</span><var><span class="pln">query</span><span class="pun">₂</span></var><span class="pln">⟩ </span><span class="roman"><span class="pun">…</span></span><span class="pln"> ⟨</span><var><span class="pln">query</span><span class="pun">ₙ</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>is satisfied by all sets of values for the pattern variables that satisfy at
least one of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">⟨</mo>
    <mspace width="0.1em"/>
    <mi>q</mi>
    <mi>u</mi>
    <mi>e</mi>
    <mi>r</mi>
    <msub>
      <mi>y</mi>
      <mn>1</mn>
    </msub>
    <mo stretchy="false">⟩</mo>
  </mrow>
</math> <span class="roman">…</span> <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">⟨</mo>
    <mspace width="0.1em"/>
    <mi>q</mi>
    <mi>u</mi>
    <mi>e</mi>
    <mi>r</mi>
    <msub>
      <mi>y</mi>
      <mi>n</mi>
    </msub>
    <mo stretchy="false">⟩</mo>
  </mrow>
</math>.
</p>
<p>Compound queries can also be formed with <code>not</code>. For example,
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">supervisor </span><span class="pun">?</span><span class="pln">x </span><span class="opn">(</span><span class="pln">Bitdiddle Ben</span><span class="clo">))</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">not </span><span class="opn">(</span><span class="pln">job </span><span class="pun">?</span><span class="pln">x </span><span class="opn">(</span><span class="pln">computer programmer</span><span class="clo">))))</span></pre></div>

<p>finds all people supervised by Ben Bitdiddle who are not computer programmers.
In general,
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">not ⟨</span><var><span class="pln">query</span><span class="pun">₁</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>is satisfied by all assignments to the pattern variables that do not satisfy
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">⟨</mo>
    <mspace width="0.1em"/>
    <mi>q</mi>
    <mi>u</mi>
    <mi>e</mi>
    <mi>r</mi>
    <msub>
      <mi>y</mi>
      <mn>1</mn>
    </msub>
    <mo stretchy="false">⟩</mo>
  </mrow>
</math>.<a class="footnote_link" id="DOCF267" href="#FOOT267"><sup>267</sup></a>
</p>
<p>The final combining form is called <code>lisp-value</code>.  When <code>lisp-value</code>
is the first element of a pattern, it specifies that the next element is a Lisp
predicate to be applied to the rest of the (instantiated) elements as
arguments.  In general,
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">lisp-value ⟨</span><var><span class="pln">predicate</span></var><span class="pln">⟩ ⟨</span><var><span class="pln">arg</span><span class="pun">₁</span></var><span class="pln">⟩ </span><span class="roman"><span class="pun">…</span></span><span class="pln"> ⟨</span><var><span class="pln">arg</span><span class="pun">ₙ</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>will be satisfied by assignments to the pattern variables for which the
<code>⟨</code><var>predicate</var><code>⟩</code> applied to the instantiated <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">⟨</mo>
    <mspace width="0.1em"/>
    <mi>a</mi>
    <mi>r</mi>
    <msub>
      <mi>g</mi>
      <mn>1</mn>
    </msub>
    <mo stretchy="false">⟩</mo>
  </mrow>
</math> <span class="roman">…</span>
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">⟨</mo>
    <mspace width="0.1em"/>
    <mi>a</mi>
    <mi>r</mi>
    <msub>
      <mi>g</mi>
      <mi>n</mi>
    </msub>
    <mo stretchy="false">⟩</mo>
  </mrow>
</math> is true.  For example, to find all people whose salary is
greater than $30,000 we could write<a class="footnote_link" id="DOCF268" href="#FOOT268"><sup>268</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">salary </span><span class="pun">?</span><span class="pln">person </span><span class="pun">?</span><span class="pln">amount</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">lisp-value </span><span class="pun">&gt;</span><span class="pln"> </span><span class="pun">?</span><span class="pln">amount </span><span class="lit">30000</span><span class="clo">))</span></pre></div>

<blockquote>
<p><strong><a id="Exercise-4_002e56"></a>Exercise 4.56:</strong> Formulate compound queries that
retrieve the following information:
</p>
<ol>
<li> the names of all people who are supervised by Ben Bitdiddle, together with
their addresses;

</li><li> all people whose salary is less than Ben Bitdiddle’s, together with their
salary and Ben Bitdiddle’s salary;

</li><li> all people who are supervised by someone who is not in the computer division,
together with the supervisor’s name and job.

</li></ol>
</blockquote>

<a id="Rules"></a>
<h5 class="subsubheading">Rules</h5>

<p>In addition to primitive queries and compound queries, the query language
provides means for abstracting queries.  These are given by <a id="index-rules-1"></a>
<em>rules</em>.
The rule
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">rule </span><span class="opn">(</span><span class="pln">lives-near </span><span class="pun">?</span><span class="pln">person-1 </span><span class="pun">?</span><span class="pln">person-2</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">address </span><span class="pun">?</span><span class="pln">person-1 
                    </span><span class="opn">(</span><span class="pun">?</span><span class="pln">town </span><span class="pun">.</span><span class="pln"> </span><span class="pun">?</span><span class="pln">rest-1</span><span class="clo">))</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">address </span><span class="pun">?</span><span class="pln">person-2 
                    </span><span class="opn">(</span><span class="pun">?</span><span class="pln">town </span><span class="pun">.</span><span class="pln"> </span><span class="pun">?</span><span class="pln">rest-2</span><span class="clo">))</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">not </span><span class="opn">(</span><span class="pln">same </span><span class="pun">?</span><span class="pln">person-1 </span><span class="pun">?</span><span class="pln">person-2</span><span class="clo">))))</span></pre></div>

<p>specifies that two people live near each other if they live in the same town.
The final <code>not</code> clause prevents the rule from saying that all people live
near themselves.  The <code>same</code> relation is defined by a very simple
rule:<a class="footnote_link" id="DOCF269" href="#FOOT269"><sup>269</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">rule </span><span class="opn">(</span><span class="pln">same </span><span class="pun">?</span><span class="pln">x </span><span class="pun">?</span><span class="pln">x</span><span class="clo">))</span></pre></div>

<p>The following rule declares that a person is a “wheel” in an organization if
he supervises someone who is in turn a supervisor:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">rule </span><span class="opn">(</span><span class="pln">wheel </span><span class="pun">?</span><span class="pln">person</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">supervisor </span><span class="pun">?</span><span class="pln">middle-manager 
                       </span><span class="pun">?</span><span class="pln">person</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">supervisor </span><span class="pun">?</span><span class="pln">x </span><span class="pun">?</span><span class="pln">middle-manager</span><span class="clo">)))</span></pre></div>

<p>The general form of a rule is
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">rule ⟨</span><var><span class="pln">conclusion</span></var><span class="pln">⟩ ⟨</span><var><span class="pln">body</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>where <code>⟨</code><var>conclusion</var><code>⟩</code> is a pattern and <code>⟨</code><var>body</var><code>⟩</code> is any
query.<a class="footnote_link" id="DOCF270" href="#FOOT270"><sup>270</sup></a> We can think of a rule as representing a large
(even infinite) set of assertions, namely all instantiations of the rule
conclusion with variable assignments that satisfy the rule body.  When we
described simple queries (patterns), we said that an assignment to variables
satisfies a pattern if the instantiated pattern is in the data base.  But the
pattern needn’t be explicitly in the data base as an assertion.  It can be an
implicit assertion implied by a rule.  For example, the query
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">lives-near </span><span class="pun">?</span><span class="pln">x </span><span class="opn">(</span><span class="pln">Bitdiddle Ben</span><span class="clo">))</span></pre></div>

<p>results in
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">lives-near </span><span class="opn">(</span><span class="pln">Reasoner Louis</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">Bitdiddle Ben</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">lives-near </span><span class="opn">(</span><span class="pln">Aull DeWitt</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">Bitdiddle Ben</span><span class="clo">))</span></pre></div>

<p>To find all computer programmers who live near Ben Bitdiddle, we can ask
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">job </span><span class="pun">?</span><span class="pln">x </span><span class="opn">(</span><span class="pln">computer programmer</span><span class="clo">))</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">lives-near </span><span class="pun">?</span><span class="pln">x </span><span class="opn">(</span><span class="pln">Bitdiddle Ben</span><span class="clo">)))</span></pre></div>

<p>As in the case of compound procedures, rules can be used as parts of other
rules (as we saw with the <code>lives-near</code> rule above) or even be defined
recursively.  For instance, the rule
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">rule </span><span class="opn">(</span><span class="pln">outranked-by </span><span class="pun">?</span><span class="pln">staff-person </span><span class="pun">?</span><span class="pln">boss</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">or</span><span class="pln"> </span><span class="opn">(</span><span class="pln">supervisor </span><span class="pun">?</span><span class="pln">staff-person </span><span class="pun">?</span><span class="pln">boss</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">supervisor </span><span class="pun">?</span><span class="pln">staff-person 
                           </span><span class="pun">?</span><span class="pln">middle-manager</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">outranked-by </span><span class="pun">?</span><span class="pln">middle-manager 
                             </span><span class="pun">?</span><span class="pln">boss</span><span class="clo">))))</span></pre></div>

<p>says that a staff person is outranked by a boss in the organization if the boss
is the person’s supervisor or (recursively) if the person’s supervisor is
outranked by the boss.
</p>
<blockquote>
<p><strong><a id="Exercise-4_002e57"></a>Exercise 4.57:</strong> Define a rule that says that
person 1 can replace person 2 if either person 1 does the same job as person 2
or someone who does person 1’s job can also do person 2’s job, and if person 1
and person 2 are not the same person. Using your rule, give queries that find
the following:
</p>
<ol>
<li> all people who can replace Cy D. Fect;

</li><li> all people who can replace someone who is being paid more than they are,
together with the two salaries.

</li></ol>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e58"></a>Exercise 4.58:</strong> Define a rule that says that a
person is a “big shot” in a division if the person works in the division but
does not have a supervisor who works in the division.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e59"></a>Exercise 4.59:</strong> Ben Bitdiddle has missed one
meeting too many.  Fearing that his habit of forgetting meetings could cost him
his job, Ben decides to do something about it.  He adds all the weekly meetings
of the firm to the Microshaft data base by asserting the following:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">meeting accounting </span><span class="opn">(</span><span class="pln">Monday </span><span class="lit">9</span><span class="pln">am</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">meeting administration </span><span class="opn">(</span><span class="pln">Monday </span><span class="lit">10</span><span class="pln">am</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">meeting computer </span><span class="opn">(</span><span class="pln">Wednesday </span><span class="lit">3</span><span class="pln">pm</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">meeting administration </span><span class="opn">(</span><span class="pln">Friday </span><span class="lit">1</span><span class="pln">pm</span><span class="clo">))</span></pre></div>

<p>Each of the above assertions is for a meeting of an entire division.  Ben also
adds an entry for the company-wide meeting that spans all the divisions.  All
of the company’s employees attend this meeting.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">meeting whole-company </span><span class="opn">(</span><span class="pln">Wednesday </span><span class="lit">4</span><span class="pln">pm</span><span class="clo">))</span></pre></div>

<ol>
<li> On Friday morning, Ben wants to query the data base for all the meetings that
occur that day.  What query should he use?

</li><li> Alyssa P. Hacker is unimpressed.  She thinks it would be much more useful to be
able to ask for her meetings by specifying her name.  So she designs a rule
that says that a person’s meetings include all <code>whole-company</code> meetings
plus all meetings of that person’s division.  Fill in the body of Alyssa’s
rule.

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">rule </span><span class="opn">(</span><span class="pln">meeting-time </span><span class="pun">?</span><span class="pln">person </span><span class="pun">?</span><span class="pln">day-and-time</span><span class="clo">)</span><span class="pln">
      ⟨</span><var><span class="pln">rule-body</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

</li><li> Alyssa arrives at work on Wednesday morning and wonders what meetings she has
to attend that day.  Having defined the above rule, what query should she make
to find this out?

</li></ol>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e60"></a>Exercise 4.60:</strong> By giving the query
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">lives-near </span><span class="pun">?</span><span class="pln">person </span><span class="opn">(</span><span class="pln">Hacker Alyssa P</span><span class="clo">))</span></pre></div>

<p>Alyssa P. Hacker is able to find people who live near her, with whom she can
ride to work.  On the other hand, when she tries to find all pairs of people
who live near each other by querying
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">lives-near </span><span class="pun">?</span><span class="pln">person-1 </span><span class="pun">?</span><span class="pln">person-2</span><span class="clo">)</span></pre></div>

<p>she notices that each pair of people who live near each other is listed twice;
for example,
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">lives-near </span><span class="opn">(</span><span class="pln">Hacker Alyssa P</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">Fect Cy D</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">lives-near </span><span class="opn">(</span><span class="pln">Fect Cy D</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">Hacker Alyssa P</span><span class="clo">))</span></pre></div>

<p>Why does this happen?  Is there a way to find a list of people who live near
each other, in which each pair appears only once?  Explain.
</p></blockquote>

<a id="Logic-as-programs"></a>
<h5 class="subsubheading">Logic as programs</h5>

<p>We can regard a rule as a kind of logical implication: <em>If</em> an assignment
of values to pattern variables satisfies the body, <em>then</em> it satisfies the
conclusion.  Consequently, we can regard the query language as having the
ability to perform <a id="index-logical-deductions"></a>
<em>logical deductions</em> based upon the rules.  As an
example, consider the <code>append</code> operation described at the beginning of
<a href="#g_t4_002e4">4.4</a>.  As we said, <code>append</code> can be characterized by the
following two rules:
</p>
<ul>
<li> For any list <code>y</code>, the empty list and <code>y</code> <code>append</code> to form
<code>y</code>.

</li><li> For any <code>u</code>, <code>v</code>, <code>y</code>, and <code>z</code>, <code>(cons u v)</code> and
<code>y</code> <code>append</code> to form <code>(cons u z)</code> if <code>v</code> and <code>y</code>
<code>append</code> to form <code>z</code>.

</li></ul>

<p>To express this in our query language, we define two rules for a relation
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">append-to-form x y z</span><span class="clo">)</span></pre></div>

<p>which we can interpret to mean “<code>x</code> and <code>y</code> <code>append</code> to form
<code>z</code>”:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">rule </span><span class="opn">(</span><span class="pln">append-to-form </span><span class="opn">(</span><span class="clo">)</span><span class="pln"> </span><span class="pun">?</span><span class="pln">y </span><span class="pun">?</span><span class="pln">y</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">rule </span><span class="opn">(</span><span class="pln">append-to-form </span><span class="opn">(</span><span class="pun">?</span><span class="pln">u </span><span class="pun">.</span><span class="pln"> </span><span class="pun">?</span><span class="pln">v</span><span class="clo">)</span><span class="pln"> </span><span class="pun">?</span><span class="pln">y </span><span class="opn">(</span><span class="pun">?</span><span class="pln">u </span><span class="pun">.</span><span class="pln"> </span><span class="pun">?</span><span class="pln">z</span><span class="clo">))</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">append-to-form </span><span class="pun">?</span><span class="pln">v </span><span class="pun">?</span><span class="pln">y </span><span class="pun">?</span><span class="pln">z</span><span class="clo">))</span></pre></div>

<p>The first rule has no body, which means that the conclusion holds for any value
of <code>?y</code>.  Note how the second rule makes use of dotted-tail notation to
name the <code>car</code> and <code>cdr</code> of a list.
</p>
<p>Given these two rules, we can formulate queries that compute the <code>append</code>
of two lists:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><i><span class="com">;;; Query input:</span></i><span class="pln">
</span><span class="opn">(</span><span class="pln">append-to-form </span><span class="opn">(</span><span class="pln">a b</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">c d</span><span class="clo">)</span><span class="pln"> </span><span class="pun">?</span><span class="pln">z</span><span class="clo">)</span><span class="pln">

</span><i><span class="com">;;; Query results:</span></i><span class="pln">
</span><span class="opn">(</span><span class="pln">append-to-form </span><span class="opn">(</span><span class="pln">a b</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">c d</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">a b c d</span><span class="clo">))</span></pre></div>

<p>What is more striking, we can use the same rules to ask the question “Which
list, when <code>append</code>ed to <code>(a b)</code>, yields <code>(a b c d)</code>?”  This is
done as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><i><span class="com">;;; Query input:</span></i><span class="pln">
</span><span class="opn">(</span><span class="pln">append-to-form </span><span class="opn">(</span><span class="pln">a b</span><span class="clo">)</span><span class="pln"> </span><span class="pun">?</span><span class="pln">y </span><span class="opn">(</span><span class="pln">a b c d</span><span class="clo">))</span><span class="pln">

</span><i><span class="com">;;; Query results:</span></i><span class="pln">
</span><span class="opn">(</span><span class="pln">append-to-form </span><span class="opn">(</span><span class="pln">a b</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">c d</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">a b c d</span><span class="clo">))</span></pre></div>

<p>We can also ask for all pairs of lists that <code>append</code> to form <code>(a b c
d)</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><i><span class="com">;;; Query input:</span></i><span class="pln">
</span><span class="opn">(</span><span class="pln">append-to-form </span><span class="pun">?</span><span class="pln">x </span><span class="pun">?</span><span class="pln">y </span><span class="opn">(</span><span class="pln">a b c d</span><span class="clo">))</span><span class="pln">

</span><i><span class="com">;;; Query results:</span></i><span class="pln">
</span><span class="opn">(</span><span class="pln">append-to-form </span><span class="opn">(</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">a b c d</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">a b c d</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">append-to-form </span><span class="opn">(</span><span class="pln">a</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">b c d</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">a b c d</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">append-to-form </span><span class="opn">(</span><span class="pln">a b</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">c d</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">a b c d</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">append-to-form </span><span class="opn">(</span><span class="pln">a b c</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">d</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">a b c d</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">append-to-form </span><span class="opn">(</span><span class="pln">a b c d</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">a b c d</span><span class="clo">))</span></pre></div>

<p>The query system may seem to exhibit quite a bit of intelligence in using the
rules to deduce the answers to the queries above.  Actually, as we will see in
the next section, the system is following a well-determined algorithm in
unraveling the rules.  Unfortunately, although the system works impressively in
the <code>append</code> case, the general methods may break down in more complex
cases, as we will see in <a href="#g_t4_002e4_002e3">4.4.3</a>.
</p>
<blockquote>
<p><strong><a id="Exercise-4_002e61"></a>Exercise 4.61:</strong> The following rules implement a
<code>next-to</code> relation that finds adjacent elements of a list:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">rule </span><span class="opn">(</span><span class="pun">?</span><span class="pln">x next-to </span><span class="pun">?</span><span class="pln">y in </span><span class="opn">(</span><span class="pun">?</span><span class="pln">x </span><span class="pun">?</span><span class="pln">y </span><span class="pun">.</span><span class="pln"> </span><span class="pun">?</span><span class="pln">u</span><span class="clo">)))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">rule </span><span class="opn">(</span><span class="pun">?</span><span class="pln">x next-to </span><span class="pun">?</span><span class="pln">y in </span><span class="opn">(</span><span class="pun">?</span><span class="pln">v </span><span class="pun">.</span><span class="pln"> </span><span class="pun">?</span><span class="pln">z</span><span class="clo">))</span><span class="pln">
      </span><span class="opn">(</span><span class="pun">?</span><span class="pln">x next-to </span><span class="pun">?</span><span class="pln">y in </span><span class="pun">?</span><span class="pln">z</span><span class="clo">))</span></pre></div>

<p>What will the response be to the following queries?
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pun">?</span><span class="pln">x next-to </span><span class="pun">?</span><span class="pln">y in </span><span class="opn">(</span><span class="lit">1</span><span class="pln"> </span><span class="opn">(</span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="clo">)</span><span class="pln"> </span><span class="lit">4</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pun">?</span><span class="pln">x next-to </span><span class="lit">1</span><span class="pln"> in </span><span class="opn">(</span><span class="lit">2</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">1</span><span class="clo">))</span></pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e62"></a>Exercise 4.62:</strong> Define rules to implement the
<code>last-pair</code> operation of <a href="2_002e2.xhtml#Exercise-2_002e17">Exercise 2.17</a>, which returns a list
containing the last element of a nonempty list.  Check your rules on queries
such as <code>(last-pair (3) ?x)</code>, <code>(last-pair (1 2 3) ?x)</code> and
<code>(last-pair (2 ?x) (3))</code>.  Do your rules work correctly on queries such as
<code>(last-pair ?x (3))</code>?
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e63"></a>Exercise 4.63:</strong> The following data base (see
Genesis 4) traces the genealogy of the descendants of Ada back to Adam, by way
of Cain:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">son Adam Cain</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">son Cain Enoch</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">son Enoch Irad</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">son Irad Mehujael</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">son Mehujael Methushael</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">son Methushael Lamech</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">wife Lamech Ada</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">son Ada Jabal</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">son Ada Jubal</span><span class="clo">)</span></pre></div>

<p>Formulate rules such as “If <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>S</mi>
</math> is the son of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math>, and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> is the son of
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>G</mi>
</math>, then <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>S</mi>
</math> is the grandson of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>G</mi>
</math>” and “If <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>W</mi>
</math> is the wife of
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>M</mi>
</math>, and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>S</mi>
</math> is the son of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>W</mi>
</math>, then <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>S</mi>
</math> is the son of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>M</mi>
</math>” (which
was supposedly more true in biblical times than today) that will enable the
query system to find the grandson of Cain; the sons of Lamech; the grandsons of
Methushael.  (See <a href="#Exercise-4_002e69">Exercise 4.69</a> for some rules to deduce more complicated
relationships.)
</p></blockquote>

<a id="g_t4_002e4_002e2"></a>
<a id="How-the-Query-System-Works"></a>
<h4 class="subsection"><span class="secnum">4.4.2</span><span class="sectitle">How the Query System Works</span></h4>

<p>In section <a href="#g_t4_002e4_002e4">4.4.4</a> we will present an implementation of the query
interpreter as a collection of procedures.  In this section we give an overview
that explains the general structure of the system independent of low-level
implementation details.  After describing the implementation of the
interpreter, we will be in a position to understand some of its limitations and
some of the subtle ways in which the query language’s logical operations differ
from the operations of mathematical logic.
</p>
<p>It should be apparent that the query evaluator must perform some kind of search
in order to match queries against facts and rules in the data base.  One way to
do this would be to implement the query system as a nondeterministic program,
using the <code>amb</code> evaluator of <a href="4_002e3.xhtml#g_t4_002e3">4.3</a> (see <a href="#Exercise-4_002e78">Exercise 4.78</a>).
Another possibility is to manage the search with the aid of streams.  Our
implementation follows this second approach.
</p>
<p>The query system is organized around two central operations called
<a id="index-pattern-matching"></a>
<em>pattern matching</em> and <a id="index-unification-1"></a>
<em>unification</em>.  We first describe
pattern matching and explain how this operation, together with the organization
of information in terms of streams of frames, enables us to implement both
simple and compound queries.  We next discuss unification, a generalization of
pattern matching needed to implement rules.  Finally, we show how the entire
query interpreter fits together through a procedure that classifies expressions
in a manner analogous to the way <code>eval</code> classifies expressions for the
interpreter described in <a href="4_002e1.xhtml#g_t4_002e1">4.1</a>.
</p>
<a id="Pattern-matching"></a>
<h5 class="subsubheading">Pattern matching</h5>

<p>A <a id="index-pattern-matcher"></a>
<em>pattern matcher</em> is a program that tests whether some datum fits a
specified pattern.  For example, the data list <code>((a b) c (a b))</code> matches
the pattern <code>(?x c ?x)</code> with the pattern variable <code>?x</code> bound to
<code>(a b)</code>.  The same data list matches the pattern <code>(?x ?y ?z)</code> with
<code>?x</code> and <code>?z</code> both bound to <code>(a b)</code> and <code>?y</code> bound to
<code>c</code>.  It also matches the pattern <code>((?x ?y) c (?x ?y))</code> with
<code>?x</code> bound to <code>a</code> and <code>?y</code> bound to <code>b</code>.  However, it does
not match the pattern <code>(?x a ?y)</code>, since that pattern specifies a list
whose second element is the symbol <code>a</code>.
</p>
<p>The pattern matcher used by the query system takes as inputs a pattern, a
datum, and a <a id="index-frame"></a>
<em>frame</em> that specifies bindings for various pattern
variables.  It checks whether the datum matches the pattern in a way that is
consistent with the bindings already in the frame.  If so, it returns the given
frame augmented by any bindings that may have been determined by the match.
Otherwise, it indicates that the match has failed.
</p>
<p>For example, using the pattern <code>(?x ?y ?x)</code> to match <code>(a b a)</code> given
an empty frame will return a frame specifying that <code>?x</code> is bound to
<code>a</code> and <code>?y</code> is bound to <code>b</code>.  Trying the match with the same
pattern, the same datum, and a frame specifying that <code>?y</code> is bound to
<code>a</code> will fail.  Trying the match with the same pattern, the same datum,
and a frame in which <code>?y</code> is bound to <code>b</code> and <code>?x</code> is unbound
will return the given frame augmented by a binding of <code>?x</code> to <code>a</code>.
</p>
<p>The pattern matcher is all the mechanism that is needed to process simple
queries that don’t involve rules.  For instance, to process the query
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">job </span><span class="pun">?</span><span class="pln">x </span><span class="opn">(</span><span class="pln">computer programmer</span><span class="clo">))</span></pre></div>

<p>we scan through all assertions in the data base and select those that match the
pattern with respect to an initially empty frame.  For each match we find, we
use the frame returned by the match to instantiate the pattern with a value for
<code>?x</code>.
</p>
<a id="Streams-of-frames"></a>
<h5 class="subsubheading">Streams of frames</h5>

<p>The testing of patterns against frames is organized through the use of streams.
Given a single frame, the matching process runs through the data-base entries
one by one.  For each data-base entry, the matcher generates either a special
symbol indicating that the match has failed or an extension to the frame.  The
results for all the data-base entries are collected into a stream, which is
passed through a filter to weed out the failures.  The result is a stream of
all the frames that extend the given frame via a match to some assertion in the
data base.<a class="footnote_link" id="DOCF271" href="#FOOT271"><sup>271</sup></a>
</p>
<p>In our system, a query takes an input stream of frames and performs the above
matching operation for every frame in the stream, as indicated in <a href="#Figure-4_002e4">Figure 4.4</a>.  
That is, for each frame in the input stream, the query generates a new
stream consisting of all extensions to that frame by matches to assertions in
the data base.  All these streams are then combined to form one huge stream,
which contains all possible extensions of every frame in the input stream.
This stream is the output of the query.
</p>
<figure class="float">
<a id="Figure-4_002e4"></a>
<object style="width: 56.21ex; height: 22.19ex;" data="fig/chap4/Fig4.4a.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 4.4:</strong> A query processes a stream of frames.</p>
</figcaption>
</figure>

<p>To answer a simple query, we use the query with an input stream consisting of a
single empty frame.  The resulting output stream contains all extensions to the
empty frame (that is, all answers to our query).  This stream of frames is then
used to generate a stream of copies of the original query pattern with the
variables instantiated by the values in each frame, and this is the stream that
is finally printed.
</p>
<a id="Compound-queries-1"></a>
<h5 class="subsubheading">Compound queries</h5>

<p>The real elegance of the stream-of-frames implementation is evident when we
deal with compound queries.  The processing of compound queries makes use of
the ability of our matcher to demand that a match be consistent with a
specified frame.  For example, to handle the <code>and</code> of two queries, such as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">can-do-job 
      </span><span class="pun">?</span><span class="pln">x 
      </span><span class="opn">(</span><span class="pln">computer programmer trainee</span><span class="clo">))</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">job </span><span class="pun">?</span><span class="pln">person </span><span class="pun">?</span><span class="pln">x</span><span class="clo">))</span></pre></div>

<p>(informally, “Find all people who can do the job of a computer programmer
trainee”), we first find all entries that match the pattern
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">can-do-job </span><span class="pun">?</span><span class="pln">x </span><span class="opn">(</span><span class="pln">computer programmer trainee</span><span class="clo">))</span></pre></div>

<p>This produces a stream of frames, each of which contains a binding for
<code>?x</code>.  Then for each frame in the stream we find all entries that match
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">job </span><span class="pun">?</span><span class="pln">person </span><span class="pun">?</span><span class="pln">x</span><span class="clo">)</span></pre></div>

<p>in a way that is consistent with the given binding for <code>?x</code>.  Each such
match will produce a frame containing bindings for <code>?x</code> and
<code>?person</code>.  The <code>and</code> of two queries can be viewed as a series
combination of the two component queries, as shown in <a href="#Figure-4_002e5">Figure 4.5</a>.  The
frames that pass through the first query filter are filtered and further
extended by the second query.
</p>
<figure class="float">
<a id="Figure-4_002e5"></a>
<object style="width: 55.69ex; height: 22.28ex;" data="fig/chap4/Fig4.5a.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 4.5:</strong> The <code>and</code> combination of two queries is produced by operating on the stream of frames in series.</p>
</figcaption>
</figure>

<p><a href="#Figure-4_002e6">Figure 4.6</a> shows the analogous method for computing the <code>or</code> of two
queries as a parallel combination of the two component queries.  The input
stream of frames is extended separately by each query.  The two resulting
streams are then merged to produce the final output stream.
</p>
<figure class="float">
<a id="Figure-4_002e6"></a>
<object style="width: 58.02ex; height: 35.92ex;" data="fig/chap4/Fig4.6a.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 4.6:</strong> The <code>or</code> combination of two queries is produced by operating on the stream of frames in parallel and merging the results.</p>
</figcaption>
</figure>

<p>Even from this high-level description, it is apparent that the processing of
compound queries can be slow.  For example, since a query may produce more than
one output frame for each input frame, and each query in an <code>and</code> gets its
input frames from the previous query, an <code>and</code> query could, in the worst
case, have to perform a number of matches that is exponential in the number of
queries (see <a href="#Exercise-4_002e76">Exercise 4.76</a>).<a class="footnote_link" id="DOCF272" href="#FOOT272"><sup>272</sup></a> Though systems for
handling only simple queries are quite practical, dealing with complex queries
is extremely difficult.<a class="footnote_link" id="DOCF273" href="#FOOT273"><sup>273</sup></a>
</p>
<p>From the stream-of-frames viewpoint, the <code>not</code> of some query acts as a
filter that removes all frames for which the query can be satisfied.  For
instance, given the pattern
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">not </span><span class="opn">(</span><span class="pln">job </span><span class="pun">?</span><span class="pln">x </span><span class="opn">(</span><span class="pln">computer programmer</span><span class="clo">)))</span></pre></div>

<p>we attempt, for each frame in the input stream, to produce extension frames
that satisfy <code>(job ?x (computer programmer))</code>.  We remove from the input
stream all frames for which such extensions exist.  The result is a stream
consisting of only those frames in which the binding for <code>?x</code> does not
satisfy <code>(job ?x (computer programmer))</code>.  For example, in processing the
query
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">supervisor </span><span class="pun">?</span><span class="pln">x </span><span class="pun">?</span><span class="pln">y</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">not </span><span class="opn">(</span><span class="pln">job </span><span class="pun">?</span><span class="pln">x </span><span class="opn">(</span><span class="pln">computer programmer</span><span class="clo">))))</span></pre></div>

<p>the first clause will generate frames with bindings for <code>?x</code> and
<code>?y</code>.  The <code>not</code> clause will then filter these by removing all frames
in which the binding for <code>?x</code> satisfies the restriction that <code>?x</code> is
a computer programmer.<a class="footnote_link" id="DOCF274" href="#FOOT274"><sup>274</sup></a>
</p>
<p>The <code>lisp-value</code> special form is implemented as a similar filter on frame
streams.  We use each frame in the stream to instantiate any variables in the
pattern, then apply the Lisp predicate.  We remove from the input stream all
frames for which the predicate fails.
</p>
<a id="Unification"></a>
<h5 class="subsubheading">Unification</h5>

<p>In order to handle rules in the query language, we must be able to find the
rules whose conclusions match a given query pattern.  Rule conclusions are like
assertions except that they can contain variables, so we will need a
generalization of pattern matching—called <a id="index-unification-2"></a>
<em>unification</em>—in which
both the “pattern” and the “datum” may contain variables.
</p>
<p>A unifier takes two patterns, each containing constants and variables, and
determines whether it is possible to assign values to the variables that will
make the two patterns equal.  If so, it returns a frame containing these
bindings.  For example, unifying <code>(?x a ?y)</code> and <code>(?y ?z a)</code> will
specify a frame in which <code>?x</code>, <code>?y</code>, and <code>?z</code> must all be bound
to <code>a</code>.  On the other hand, unifying <code>(?x ?y a)</code> and <code>(?x b ?y)</code>
will fail, because there is no value for <code>?y</code> that can make the two
patterns equal.  (For the second elements of the patterns to be equal,
<code>?y</code> would have to be <code>b</code>; however, for the third elements to be
equal, <code>?y</code> would have to be <code>a</code>.)  The unifier used in the query
system, like the pattern matcher, takes a frame as input and performs
unifications that are consistent with this frame.
</p>
<p>The unification algorithm is the most technically difficult part of the query
system.  With complex patterns, performing unification may seem to require
deduction.  To unify <code>(?x ?x)</code> and <code>((a ?y c) (a b ?z))</code>, for
example, the algorithm must infer that <code>?x</code> should be <code>(a b c)</code>,
<code>?y</code> should be <code>b</code>, and <code>?z</code> should be <code>c</code>.  We may think
of this process as solving a set of equations among the pattern components.  In
general, these are simultaneous equations, which may require substantial
manipulation to solve.<a class="footnote_link" id="DOCF275" href="#FOOT275"><sup>275</sup></a> For example, unifying <code>(?x ?x)</code> and
<code>((a ?y c) (a b ?z))</code> may be thought of as specifying the simultaneous
equations
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pun">?</span><span class="pln">x </span><span class="pun">=</span><span class="pln"> </span><span class="opn">(</span><span class="pln">a </span><span class="pun">?</span><span class="pln">y c</span><span class="clo">)</span><span class="pln">
</span><span class="pun">?</span><span class="pln">x </span><span class="pun">=</span><span class="pln"> </span><span class="opn">(</span><span class="pln">a b </span><span class="pun">?</span><span class="pln">z</span><span class="clo">)</span></pre></div>

<p>These equations imply that
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">a </span><span class="pun">?</span><span class="pln">y c</span><span class="clo">)</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> </span><span class="opn">(</span><span class="pln">a b </span><span class="pun">?</span><span class="pln">z</span><span class="clo">)</span></pre></div>

<p>which in turn implies that
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">a </span><span class="pun">=</span><span class="pln"> a</span><span class="pun">,</span><span class="pln"> </span><span class="pun">?</span><span class="pln">y </span><span class="pun">=</span><span class="pln"> b</span><span class="pun">,</span><span class="pln"> c </span><span class="pun">=</span><span class="pln"> </span><span class="pun">?</span><span class="pln">z</span><span class="pun">,</span></pre></div>

<p>and hence that
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pun">?</span><span class="pln">x </span><span class="pun">=</span><span class="pln"> </span><span class="opn">(</span><span class="pln">a b c</span><span class="clo">)</span></pre></div>

<p>In a successful pattern match, all pattern variables become bound, and the
values to which they are bound contain only constants.  This is also true of
all the examples of unification we have seen so far.  In general, however, a
successful unification may not completely determine the variable values; some
variables may remain unbound and others may be bound to values that contain
variables.
</p>
<p>Consider the unification of <code>(?x a)</code> and <code>((b ?y) ?z)</code>.  We can
deduce that <code>?x = (b ?y)</code> and <code>a = ?z</code>, but we cannot further solve
for <code>?x</code> or <code>?y</code>.  The unification doesn’t fail, since it is
certainly possible to make the two patterns equal by assigning values to
<code>?x</code> and <code>?y</code>.  Since this match in no way restricts the values
<code>?y</code> can take on, no binding for <code>?y</code> is put into the result frame.
The match does, however, restrict the value of <code>?x</code>.  Whatever value
<code>?y</code> has, <code>?x</code> must be <code>(b ?y)</code>.  A binding of <code>?x</code> to the
pattern <code>(b ?y)</code> is thus put into the frame.  If a value for <code>?y</code> is
later determined and added to the frame (by a pattern match or unification that
is required to be consistent with this frame), the previously bound <code>?x</code>
will refer to this value.<a class="footnote_link" id="DOCF276" href="#FOOT276"><sup>276</sup></a>
</p>
<a id="Applying-rules"></a>
<h5 class="subsubheading">Applying rules</h5>

<p>Unification is the key to the component of the query system that makes
inferences from rules. To see how this is accomplished, consider processing a
query that involves applying a rule, such as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">lives-near </span><span class="pun">?</span><span class="pln">x </span><span class="opn">(</span><span class="pln">Hacker Alyssa P</span><span class="clo">))</span></pre></div>

<p>To process this query, we first use the ordinary pattern-match procedure
described above to see if there are any assertions in the data base that match
this pattern.  (There will not be any in this case, since our data base
includes no direct assertions about who lives near whom.)  The next step is to
attempt to unify the query pattern with the conclusion of each rule.  We find
that the pattern unifies with the conclusion of the rule
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">rule </span><span class="opn">(</span><span class="pln">lives-near </span><span class="pun">?</span><span class="pln">person-1 </span><span class="pun">?</span><span class="pln">person-2</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">address </span><span class="pun">?</span><span class="pln">person-1 
                    </span><span class="opn">(</span><span class="pun">?</span><span class="pln">town </span><span class="pun">.</span><span class="pln"> </span><span class="pun">?</span><span class="pln">rest-1</span><span class="clo">))</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">address </span><span class="pun">?</span><span class="pln">person-2 
                    </span><span class="opn">(</span><span class="pun">?</span><span class="pln">town </span><span class="pun">.</span><span class="pln"> </span><span class="pun">?</span><span class="pln">rest-2</span><span class="clo">))</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">not </span><span class="opn">(</span><span class="pln">same </span><span class="pun">?</span><span class="pln">person-1 </span><span class="pun">?</span><span class="pln">person-2</span><span class="clo">))))</span></pre></div>

<p>resulting in a frame specifying that <code>?person-2</code> is bound to <code>(Hacker
Alyssa P)</code> and that <code>?x</code> should be bound to (have the same value as)
<code>?person-1</code>.  Now, relative to this frame, we evaluate the compound query
given by the body of the rule.  Successful matches will extend this frame by
providing a binding for <code>?person-1</code>, and consequently a value for
<code>?x</code>, which we can use to instantiate the original query pattern.
</p>
<p>In general, the query evaluator uses the following method to apply a rule when
trying to establish a query pattern in a frame that specifies bindings for some
of the pattern variables:
</p>
<ul>
<li> Unify the query with the conclusion of the rule to form, if successful, an
extension of the original frame.

</li><li> Relative to the extended frame, evaluate the query formed by the body of the
rule.

</li></ul>

<p>Notice how similar this is to the method for applying a procedure in the
<code>eval</code>/<code>apply</code> evaluator for Lisp:
</p>
<ul>
<li> Bind the procedure’s parameters to its arguments to form a frame that extends
the original procedure environment.

</li><li> Relative to the extended environment, evaluate the expression formed by the
body of the procedure.

</li></ul>

<p>The similarity between the two evaluators should come as no surprise.  Just as
procedure definitions are the means of abstraction in Lisp, rule definitions
are the means of abstraction in the query language.  In each case, we unwind
the abstraction by creating appropriate bindings and evaluating the rule or
procedure body relative to these.
</p>
<a id="Simple-queries-1"></a>
<h5 class="subsubheading">Simple queries</h5>

<p>We saw earlier in this section how to evaluate simple queries in the absence of
rules.  Now that we have seen how to apply rules, we can describe how to
evaluate simple queries by using both rules and assertions.
</p>
<p>Given the query pattern and a stream of frames, we produce, for each frame in
the input stream, two streams:
</p>
<ul>
<li> a stream of extended frames obtained by matching the pattern against all
assertions in the data base (using the pattern matcher), and

</li><li> a stream of extended frames obtained by applying all possible rules (using the
unifier).<a class="footnote_link" id="DOCF277" href="#FOOT277"><sup>277</sup></a>

</li></ul>

<p>Appending these two streams produces a stream that consists of all the ways
that the given pattern can be satisfied consistent with the original frame.
These streams (one for each frame in the input stream) are now all combined to
form one large stream, which therefore consists of all the ways that any of the
frames in the original input stream can be extended to produce a match with the
given pattern.
</p>
<a id="The-query-evaluator-and-the-driver-loop"></a>
<h5 class="subsubheading">The query evaluator and the driver loop</h5>

<p>Despite the complexity of the underlying matching operations, the system is
organized much like an evaluator for any language.  The procedure that
coordinates the matching operations is called <code>qeval</code>, and it plays a role
analogous to that of the <code>eval</code> procedure for Lisp.  <code>Qeval</code> takes as
inputs a query and a stream of frames.  Its output is a stream of frames,
corresponding to successful matches to the query pattern, that extend some
frame in the input stream, as indicated in <a href="#Figure-4_002e4">Figure 4.4</a>.  Like <code>eval</code>,
<code>qeval</code> classifies the different types of expressions (queries) and
dispatches to an appropriate procedure for each.  There is a procedure for each
special form (<code>and</code>, <code>or</code>, <code>not</code>, and <code>lisp-value</code>) and one
for simple queries.
</p>
<p>The driver loop, which is analogous to the <code>driver-loop</code> procedure for the
other evaluators in this chapter, reads queries from the terminal.  For each
query, it calls <code>qeval</code> with the query and a stream that consists of a
single empty frame.  This will produce the stream of all possible matches (all
possible extensions to the empty frame).  For each frame in the resulting
stream, it instantiates the original query using the values of the variables
found in the frame.  This stream of instantiated queries is then
printed.<a class="footnote_link" id="DOCF278" href="#FOOT278"><sup>278</sup></a>
</p>
<p>The driver also checks for the special command <code>assert!</code>, which signals
that the input is not a query but rather an assertion or rule to be added to
the data base.  For instance,
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">assert!
 </span><span class="opn">(</span><span class="pln">job </span><span class="opn">(</span><span class="pln">Bitdiddle Ben</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">computer wizard</span><span class="clo">)))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">assert!
 </span><span class="opn">(</span><span class="pln">rule </span><span class="opn">(</span><span class="pln">wheel </span><span class="pun">?</span><span class="pln">person</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">supervisor 
             </span><span class="pun">?</span><span class="pln">middle-manager </span><span class="pun">?</span><span class="pln">person</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">supervisor
             </span><span class="pun">?</span><span class="pln">x </span><span class="pun">?</span><span class="pln">middle-manager</span><span class="clo">))))</span></pre></div>

<a id="g_t4_002e4_002e3"></a>
<a id="Is-Logic-Programming-Mathematical-Logic_003f"></a>
<h4 class="subsection"><span class="secnum">4.4.3</span><span class="sectitle">Is Logic Programming Mathematical Logic?</span></h4>

<p>The means of combination used in the query language may at first seem identical
to the operations <code>and</code>, <code>or</code>, and <code>not</code> of mathematical logic,
and the application of query-language rules is in fact accomplished through a
legitimate method of inference.<a class="footnote_link" id="DOCF279" href="#FOOT279"><sup>279</sup></a> This
identification of the query language with mathematical logic is not really
valid, though, because the query language provides a <a id="index-control-structure"></a>
<em>control structure</em> 
that interprets the logical statements procedurally.  We can often
take advantage of this control structure.  For example, to find all of the
supervisors of programmers we could formulate a query in either of two
logically equivalent forms:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">job </span><span class="pun">?</span><span class="pln">x </span><span class="opn">(</span><span class="pln">computer programmer</span><span class="clo">))</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">supervisor </span><span class="pun">?</span><span class="pln">x </span><span class="pun">?</span><span class="pln">y</span><span class="clo">))</span></pre></div>

<p>or
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">supervisor </span><span class="pun">?</span><span class="pln">x </span><span class="pun">?</span><span class="pln">y</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">job </span><span class="pun">?</span><span class="pln">x </span><span class="opn">(</span><span class="pln">computer programmer</span><span class="clo">)))</span></pre></div>

<p>If a company has many more supervisors than programmers (the usual case), it is
better to use the first form rather than the second because the data base must
be scanned for each intermediate result (frame) produced by the first clause of
the <code>and</code>.
</p>
<p>The aim of logic programming is to provide the programmer with techniques for
decomposing a computational problem into two separate problems: “what” is to
be computed, and “how” this should be computed.  This is accomplished by
selecting a subset of the statements of mathematical logic that is powerful
enough to be able to describe anything one might want to compute, yet weak
enough to have a controllable procedural interpretation.  The intention here is
that, on the one hand, a program specified in a logic programming language
should be an effective program that can be carried out by a computer.  Control
(“how” to compute) is effected by using the order of evaluation of the
language.  We should be able to arrange the order of clauses and the order of
subgoals within each clause so that the computation is done in an order deemed
to be effective and efficient.  At the same time, we should be able to view the
result of the computation (“what” to compute) as a simple consequence of the
laws of logic.
</p>
<p>Our query language can be regarded as just such a procedurally interpretable
subset of mathematical logic.  An assertion represents a simple fact (an atomic
proposition).  A rule represents the implication that the rule conclusion holds
for those cases where the rule body holds.  A rule has a natural procedural
interpretation: To establish the conclusion of the rule, establish the body of
the rule.  Rules, therefore, specify computations.  However, because rules can
also be regarded as statements of mathematical logic, we can justify any
“inference” accomplished by a logic program by asserting that the same result
could be obtained by working entirely within mathematical logic.<a class="footnote_link" id="DOCF280" href="#FOOT280"><sup>280</sup></a>
</p>
<a id="Infinite-loops"></a>
<h5 class="subsubheading">Infinite loops</h5>

<p>A consequence of the procedural interpretation of logic programs is that it is
possible to construct hopelessly inefficient programs for solving certain
problems.  An extreme case of inefficiency occurs when the system falls into
infinite loops in making deductions.  As a simple example, suppose we are
setting up a data base of famous marriages, including
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">assert! </span><span class="opn">(</span><span class="pln">married Minnie Mickey</span><span class="clo">))</span></pre></div>

<p>If we now ask
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">married Mickey </span><span class="pun">?</span><span class="pln">who</span><span class="clo">)</span></pre></div>

<p>we will get no response, because the system doesn’t know that if <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>A</mi>
</math> is
married to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>B</mi>
</math>, then <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>B</mi>
</math> is married to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>A</mi>
</math>.  So we assert the rule
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">assert! </span><span class="opn">(</span><span class="pln">rule </span><span class="opn">(</span><span class="pln">married </span><span class="pun">?</span><span class="pln">x </span><span class="pun">?</span><span class="pln">y</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">married </span><span class="pun">?</span><span class="pln">y </span><span class="pun">?</span><span class="pln">x</span><span class="clo">)))</span></pre></div>

<p>and again query
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">married Mickey </span><span class="pun">?</span><span class="pln">who</span><span class="clo">)</span></pre></div>

<p>Unfortunately, this will drive the system into an infinite loop, as follows:
</p>
<ul>
<li> The system finds that the <code>married</code> rule is applicable; that is, the rule
conclusion <code>(married ?x ?y)</code> successfully unifies with the query pattern
<code>(married Mickey ?who)</code> to produce a frame in which <code>?x</code> is bound to
<code>Mickey</code> and <code>?y</code> is bound to <code>?who</code>.  So the interpreter
proceeds to evaluate the rule body <code>(married ?y ?x)</code> in this frame—in
effect, to process the query <code>(married ?who Mickey)</code>.

</li><li> One answer appears directly as an assertion in the data base: <code>(married
Minnie Mickey)</code>.

</li><li> The <code>married</code> rule is also applicable, so the interpreter again evaluates
the rule body, which this time is equivalent to <code>(married Mickey ?who)</code>.

</li></ul>

<p>The system is now in an infinite loop.  Indeed, whether the system will find
the simple answer <code>(married Minnie Mickey)</code> before it goes into the loop
depends on implementation details concerning the order in which the system
checks the items in the data base.  This is a very simple example of the kinds
of loops that can occur.  Collections of interrelated rules can lead to loops
that are much harder to anticipate, and the appearance of a loop can depend on
the order of clauses in an <code>and</code> (see <a href="#Exercise-4_002e64">Exercise 4.64</a>) or on low-level
details concerning the order in which the system processes
queries.<a class="footnote_link" id="DOCF281" href="#FOOT281"><sup>281</sup></a>
</p>
<a id="Problems-with-not"></a>
<h5 class="subsubheading">Problems with <code>not</code></h5>

<p>Another quirk in the query system concerns <code>not</code>.  Given the data base of
<a href="#g_t4_002e4_002e1">4.4.1</a>, consider the following two queries:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">supervisor </span><span class="pun">?</span><span class="pln">x </span><span class="pun">?</span><span class="pln">y</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">not </span><span class="opn">(</span><span class="pln">job </span><span class="pun">?</span><span class="pln">x </span><span class="opn">(</span><span class="pln">computer programmer</span><span class="clo">))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">not </span><span class="opn">(</span><span class="pln">job </span><span class="pun">?</span><span class="pln">x </span><span class="opn">(</span><span class="pln">computer programmer</span><span class="clo">)))</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">supervisor </span><span class="pun">?</span><span class="pln">x </span><span class="pun">?</span><span class="pln">y</span><span class="clo">))</span></pre></div>

<p>These two queries do not produce the same result.  The first query begins by
finding all entries in the data base that match <code>(supervisor ?x ?y)</code>, and
then filters the resulting frames by removing the ones in which the value of
<code>?x</code> satisfies <code>(job ?x (computer programmer))</code>.  The second query
begins by filtering the incoming frames to remove those that can satisfy
<code>(job ?x (computer programmer))</code>.  Since the only incoming frame is empty,
it checks the data base to see if there are any patterns that satisfy
<code>(job ?x (computer programmer))</code>.  Since there generally are entries of
this form, the <code>not</code> clause filters out the empty frame and returns an
empty stream of frames.  Consequently, the entire compound query returns an
empty stream.
</p>
<p>The trouble is that our implementation of <code>not</code> really is meant to serve
as a filter on values for the variables.  If a <code>not</code> clause is processed
with a frame in which some of the variables remain unbound (as does <code>?x</code>
in the example above), the system will produce unexpected results. Similar
problems occur with the use of <code>lisp-value</code>—the Lisp predicate can’t
work if some of its arguments are unbound.  See <a href="#Exercise-4_002e77">Exercise 4.77</a>.
</p>
<p>There is also a much more serious way in which the <code>not</code> of the query
language differs from the <code>not</code> of mathematical logic.  In logic, we
interpret the statement “not <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>P</mi>
</math>” to mean that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>P</mi>
</math> is not true.  In the
query system, however, “not <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>P</mi>
</math>” means that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>P</mi>
</math> is not deducible from the
knowledge in the data base.  For example, given the personnel data base of
<a href="#g_t4_002e4_002e1">4.4.1</a>, the system would happily deduce all sorts of <code>not</code>
statements, such as that Ben Bitdiddle is not a baseball fan, that it is not
raining outside, and that 2 + 2 is not 4.<a class="footnote_link" id="DOCF282" href="#FOOT282"><sup>282</sup></a> In other words, the <code>not</code> of logic programming
languages reflects the so-called <a id="index-closed-world-assumption"></a>
<em>closed world assumption</em> that all
relevant information has been included in the data base.<a class="footnote_link" id="DOCF283" href="#FOOT283"><sup>283</sup></a>
</p>
<blockquote>
<p><strong><a id="Exercise-4_002e64"></a>Exercise 4.64:</strong> Louis Reasoner mistakenly deletes
the <code>outranked-by</code> rule (<a href="#g_t4_002e4_002e1">4.4.1</a>) from the data base.  When he
realizes this, he quickly reinstalls it.  Unfortunately, he makes a slight
change in the rule, and types it in as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">rule </span><span class="opn">(</span><span class="pln">outranked-by </span><span class="pun">?</span><span class="pln">staff-person </span><span class="pun">?</span><span class="pln">boss</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">or</span><span class="pln"> </span><span class="opn">(</span><span class="pln">supervisor </span><span class="pun">?</span><span class="pln">staff-person </span><span class="pun">?</span><span class="pln">boss</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">outranked-by </span><span class="pun">?</span><span class="pln">middle-manager
                         </span><span class="pun">?</span><span class="pln">boss</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">supervisor </span><span class="pun">?</span><span class="pln">staff-person 
                       </span><span class="pun">?</span><span class="pln">middle-manager</span><span class="clo">))))</span></pre></div>

<p>Just after Louis types this information into the system, DeWitt Aull comes by
to find out who outranks Ben Bitdiddle. He issues the query
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">outranked-by </span><span class="opn">(</span><span class="pln">Bitdiddle Ben</span><span class="clo">)</span><span class="pln"> </span><span class="pun">?</span><span class="pln">who</span><span class="clo">)</span></pre></div>

<p>After answering, the system goes into an infinite loop.  Explain why.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e65"></a>Exercise 4.65:</strong> Cy D. Fect, looking forward to
the day when he will rise in the organization, gives a query to find all the
wheels (using the <code>wheel</code> rule of <a href="#g_t4_002e4_002e1">4.4.1</a>):
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">wheel </span><span class="pun">?</span><span class="pln">who</span><span class="clo">)</span></pre></div>

<p>To his surprise, the system responds
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><i><span class="com">;;; Query results:</span></i><span class="pln">
</span><span class="opn">(</span><span class="pln">wheel </span><span class="opn">(</span><span class="pln">Warbucks Oliver</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">wheel </span><span class="opn">(</span><span class="pln">Bitdiddle Ben</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">wheel </span><span class="opn">(</span><span class="pln">Warbucks Oliver</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">wheel </span><span class="opn">(</span><span class="pln">Warbucks Oliver</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">wheel </span><span class="opn">(</span><span class="pln">Warbucks Oliver</span><span class="clo">))</span></pre></div>

<p>Why is Oliver Warbucks listed four times?
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e66"></a>Exercise 4.66:</strong> Ben has been generalizing the
query system to provide statistics about the company.  For example, to find the
total salaries of all the computer programmers one will be able to say
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">sum </span><span class="pun">?</span><span class="pln">amount
     </span><span class="opn">(</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">job </span><span class="pun">?</span><span class="pln">x </span><span class="opn">(</span><span class="pln">computer programmer</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">salary </span><span class="pun">?</span><span class="pln">x </span><span class="pun">?</span><span class="pln">amount</span><span class="clo">)))</span></pre></div>

<p>In general, Ben’s new system allows expressions of the form
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">accumulation-function ⟨</span><var><span class="pln">variable</span></var><span class="pln">⟩
                       ⟨</span><var><span class="pln">query pattern</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>where <code>accumulation-function</code> can be things like <code>sum</code>,
<code>average</code>, or <code>maximum</code>.  Ben reasons that it should be a cinch to
implement this.  He will simply feed the query pattern to <code>qeval</code>.  This
will produce a stream of frames.  He will then pass this stream through a
mapping function that extracts the value of the designated variable from each
frame in the stream and feed the resulting stream of values to the accumulation
function.  Just as Ben completes the implementation and is about to try it out,
Cy walks by, still puzzling over the <code>wheel</code> query result in 
<a href="#Exercise-4_002e65">Exercise 4.65</a>.  When Cy shows Ben the system’s response, Ben groans,
“Oh, no, my simple accumulation scheme won’t work!”
</p>
<p>What has Ben just realized?  Outline a method he can use to salvage the
situation.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e67"></a>Exercise 4.67:</strong> Devise a way to install a loop
detector in the query system so as to avoid the kinds of simple loops
illustrated in the text and in <a href="#Exercise-4_002e64">Exercise 4.64</a>.  The general idea is that
the system should maintain some sort of history of its current chain of
deductions and should not begin processing a query that it is already working
on.  Describe what kind of information (patterns and frames) is included in
this history, and how the check should be made.  (After you study the details
of the query-system implementation in <a href="#g_t4_002e4_002e4">4.4.4</a>, you may want to
modify the system to include your loop detector.)
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e68"></a>Exercise 4.68:</strong> Define rules to implement the
<code>reverse</code> operation of <a href="2_002e2.xhtml#Exercise-2_002e18">Exercise 2.18</a>, which returns a list
containing the same elements as a given list in reverse order.  (Hint: Use
<code>append-to-form</code>.)  Can your rules answer both <code>(reverse (1 2 3) ?x)</code>
and <code>(reverse ?x (1 2 3))</code>?
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e69"></a>Exercise 4.69:</strong> Beginning with the data base and
the rules you formulated in <a href="#Exercise-4_002e63">Exercise 4.63</a>, devise a rule for adding
“greats” to a grandson relationship. This should enable the system to deduce
that Irad is the great-grandson of Adam, or that Jabal and Jubal are the
great-great-great-great-great-grandsons of Adam.  (Hint: Represent the fact
about Irad, for example, as <code>((great grandson) Adam Irad)</code>.  Write rules
that determine if a list ends in the word <code>grandson</code>.  Use this to express
a rule that allows one to derive the relationship <code>((great .  ?rel) ?x
?y)</code>, where <code>?rel</code> is a list ending in <code>grandson</code>.)  Check your rules
on queries such as <code>((great grandson) ?g ?ggs)</code> and <code>(?relationship
Adam Irad)</code>.
</p></blockquote>

<a id="g_t4_002e4_002e4"></a>
<a id="Implementing-the-Query-System"></a>
<h4 class="subsection"><span class="secnum">4.4.4</span><span class="sectitle">Implementing the Query System</span></h4>

<p>Section <a href="#g_t4_002e4_002e2">4.4.2</a> described how the query system works. Now we fill in the
details by presenting a complete implementation of the system.
</p>

<a id="g_t4_002e4_002e4_002e1"></a>
<a id="The-Driver-Loop-and-Instantiation"></a>
<h5 class="subsubsection"><span class="secnum">4.4.4.1</span><span class="sectitle">The Driver Loop and Instantiation</span></h5>

<p>The driver loop for the query system repeatedly reads input expressions.  If
the expression is a rule or assertion to be added to the data base, then the
information is added.  Otherwise the expression is assumed to be a query.  The
driver passes this query to the evaluator <code>qeval</code> together with an initial
frame stream consisting of a single empty frame.  The result of the evaluation
is a stream of frames generated by satisfying the query with variable values
found in the data base.  These frames are used to form a new stream consisting
of copies of the original query in which the variables are instantiated with
values supplied by the stream of frames, and this final stream is printed at
the terminal:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> input-prompt  </span><span class="str">";;; Query input:"</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> output-prompt </span><span class="str">";;; Query results:"</span><span class="clo">)</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">query-driver-loop</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">prompt-for-input input-prompt</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">q </span><span class="opn">(</span><span class="pln">query-syntax-process </span><span class="opn">(</span><span class="pln">read</span><span class="clo">))))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">assertion-to-be-added? q</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">add-rule-or-assertion! 
            </span><span class="opn">(</span><span class="pln">add-assertion-body q</span><span class="clo">))</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">newline</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">display 
            </span><span class="str">"Assertion added to data base."</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">query-driver-loop</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">else</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">newline</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">display output-prompt</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">display-stream
            </span><span class="opn">(</span><span class="pln">stream-map
             </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">frame</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">instantiate
                q
                frame
                </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">v f</span><span class="clo">)</span><span class="pln">
                  </span><span class="opn">(</span><span class="pln">contract-question-mark v</span><span class="clo">))))</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">qeval q </span><span class="opn">(</span><span class="pln">singleton-stream </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)))))</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">query-driver-loop</span><span class="clo">)))))</span></pre></div>

<p>Here, as in the other evaluators in this chapter, we use an abstract syntax for
the expressions of the query language.  The implementation of the expression
syntax, including the predicate <code>assertion-to-be-added?</code> and the selector
<code>add-assertion-body</code>, is given in <a href="#g_t4_002e4_002e4_002e7">4.4.4.7</a>.
<code>Add-rule-or-assertion!</code> is defined in <a href="#g_t4_002e4_002e4_002e5">4.4.4.5</a>.
</p>
<p>Before doing any processing on an input expression, the driver loop transforms
it syntactically into a form that makes the processing more efficient.  This
involves changing the representation of pattern variables.  When the query is
instantiated, any variables that remain unbound are transformed back to the
input representation before being printed.  These transformations are performed
by the two procedures <code>query-syntax-process</code> and
<code>contract-question-mark</code> (<a href="#g_t4_002e4_002e4_002e7">4.4.4.7</a>).
</p>
<p>To instantiate an expression, we copy it, replacing any variables in the
expression by their values in a given frame.  The values are themselves
instantiated, since they could contain variables (for example, if <code>?x</code> in
<code>exp</code> is bound to <code>?y</code> as the result of unification and <code>?y</code> is
in turn bound to 5).  The action to take if a variable cannot be instantiated
is given by a procedural argument to <code>instantiate</code>.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">instantiate 
         exp frame unbound-var-handler</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">copy exp</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">var? exp</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">binding 
                  </span><span class="opn">(</span><span class="pln">binding-in-frame 
                   exp frame</span><span class="clo">)))</span><span class="pln">
             </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> binding
                 </span><span class="opn">(</span><span class="pln">copy 
                  </span><span class="opn">(</span><span class="pln">binding-value binding</span><span class="clo">))</span><span class="pln">
                 </span><span class="opn">(</span><span class="pln">unbound-var-handler 
                  exp frame</span><span class="clo">))))</span><span class="pln">
          </span><span class="opn">((</span><span class="pln">pair? exp</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="pln">copy </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> exp</span><span class="clo">))</span><span class="pln"> 
                 </span><span class="opn">(</span><span class="pln">copy </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> exp</span><span class="clo">))))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> exp</span><span class="clo">)))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">copy exp</span><span class="clo">))</span></pre></div>

<p>The procedures that manipulate bindings are defined in <a href="#g_t4_002e4_002e4_002e8">4.4.4.8</a>.
</p>
<a id="g_t4_002e4_002e4_002e2"></a>
<a id="The-Evaluator"></a>
<h5 class="subsubsection"><span class="secnum">4.4.4.2</span><span class="sectitle">The Evaluator</span></h5>

<p>The <code>qeval</code> procedure, called by the <code>query-driver-loop</code>, is the
basic evaluator of the query system.  It takes as inputs a query and a stream
of frames, and it returns a stream of extended frames.  It identifies special
forms by a data-directed dispatch using <code>get</code> and <code>put</code>, just as we
did in implementing generic operations in <a href="Chapter-2.xhtml#Chapter-2">Chapter 2</a>.  Any query that is
not identified as a special form is assumed to be a simple query, to be
processed by <code>simple-query</code>.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">qeval query frame-stream</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">qproc </span><span class="opn">(</span><span class="pln">get </span><span class="opn">(</span><span class="pln">type query</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'qeval</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> qproc
        </span><span class="opn">(</span><span class="pln">qproc </span><span class="opn">(</span><span class="pln">contents query</span><span class="clo">)</span><span class="pln"> frame-stream</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">simple-query query frame-stream</span><span class="clo">))))</span></pre></div>

<p><code>Type</code> and <code>contents</code>, defined in <a href="#g_t4_002e4_002e4_002e7">4.4.4.7</a>, implement
the abstract syntax of the special forms.
</p>
<a id="Simple-queries-2"></a>
<h5 class="subsubheading">Simple queries</h5>

<p>The <code>simple-query</code> procedure handles simple queries.  It takes as
arguments a simple query (a pattern) together with a stream of frames, and it
returns the stream formed by extending each frame by all data-base matches of
the query.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">simple-query query-pattern 
                      frame-stream</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">stream-flatmap
   </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">frame</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">stream-append-delayed
      </span><span class="opn">(</span><span class="pln">find-assertions query-pattern frame</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">delay</span><span class="pln"> 
        </span><span class="opn">(</span><span class="pln">apply-rules query-pattern frame</span><span class="clo">))))</span><span class="pln">
   frame-stream</span><span class="clo">))</span></pre></div>

<p>For each frame in the input stream, we use <code>find-assertions</code> 
(<a href="#g_t4_002e4_002e4_002e3">4.4.4.3</a>) to match the pattern against all assertions in the data base,
producing a stream of extended frames, and we use <code>apply-rules</code> 
(<a href="#g_t4_002e4_002e4_002e4">4.4.4.4</a>) to apply all possible rules, producing another stream of
extended frames.  These two streams are combined (using
<code>stream-append-delayed</code>, <a href="#g_t4_002e4_002e4_002e6">4.4.4.6</a>) to make a stream of all
the ways that the given pattern can be satisfied consistent with the original
frame (see <a href="#Exercise-4_002e71">Exercise 4.71</a>).  The streams for the individual input frames
are combined using <code>stream-flatmap</code> (<a href="#g_t4_002e4_002e4_002e6">4.4.4.6</a>) to form one
large stream of all the ways that any of the frames in the original input
stream can be extended to produce a match with the given pattern.
</p>
<a id="Compound-queries-2"></a>
<h5 class="subsubheading">Compound queries</h5>

<p><code>And</code> queries are handled as illustrated in <a href="#Figure-4_002e5">Figure 4.5</a> by the
<code>conjoin</code> procedure.  <code>Conjoin</code> takes as inputs the conjuncts and the
frame stream and returns the stream of extended frames.  First, <code>conjoin</code>
processes the stream of frames to find the stream of all possible frame
extensions that satisfy the first query in the conjunction.  Then, using this
as the new frame stream, it recursively applies <code>conjoin</code> to the rest of
the queries.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">conjoin conjuncts frame-stream</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">empty-conjunction? conjuncts</span><span class="clo">)</span><span class="pln">
      frame-stream
      </span><span class="opn">(</span><span class="pln">conjoin </span><span class="opn">(</span><span class="pln">rest-conjuncts conjuncts</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">qeval 
                </span><span class="opn">(</span><span class="pln">first-conjunct conjuncts</span><span class="clo">)</span><span class="pln">
                frame-stream</span><span class="clo">))))</span></pre></div>

<p>The expression
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">put </span><span class="lit">'and</span><span class="pln"> </span><span class="lit">'qeval</span><span class="pln"> conjoin</span><span class="clo">)</span></pre></div>

<p>sets up <code>qeval</code> to dispatch to <code>conjoin</code> when an <code>and</code> form is
encountered.
</p>
<p><code>Or</code> queries are handled similarly, as shown in <a href="#Figure-4_002e6">Figure 4.6</a>.  The
output streams for the various disjuncts of the <code>or</code> are computed
separately and merged using the <code>interleave-delayed</code> procedure from
<a href="#g_t4_002e4_002e4_002e6">4.4.4.6</a>.  (See <a href="#Exercise-4_002e71">Exercise 4.71</a> and <a href="#Exercise-4_002e72">Exercise 4.72</a>.)
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">disjoin disjuncts frame-stream</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">empty-disjunction? disjuncts</span><span class="clo">)</span><span class="pln">
      the-empty-stream
      </span><span class="opn">(</span><span class="pln">interleave-delayed
       </span><span class="opn">(</span><span class="pln">qeval </span><span class="opn">(</span><span class="pln">first-disjunct disjuncts</span><span class="clo">)</span><span class="pln"> 
              frame-stream</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="kwd">delay</span><span class="pln"> </span><span class="opn">(</span><span class="pln">disjoin 
               </span><span class="opn">(</span><span class="pln">rest-disjuncts disjuncts</span><span class="clo">)</span><span class="pln">
               frame-stream</span><span class="clo">)))))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">put </span><span class="lit">'or</span><span class="pln"> </span><span class="lit">'qeval</span><span class="pln"> disjoin</span><span class="clo">)</span></pre></div>

<p>The predicates and selectors for the syntax of conjuncts and disjuncts are
given in <a href="#g_t4_002e4_002e4_002e7">4.4.4.7</a>.
</p>
<a id="Filters"></a>
<h5 class="subsubheading">Filters</h5>

<p><code>Not</code> is handled by the method outlined in <a href="#g_t4_002e4_002e2">4.4.2</a>.  We
attempt to extend each frame in the input stream to satisfy the query being
negated, and we include a given frame in the output stream only if it cannot be
extended.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">negate operands frame-stream</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">stream-flatmap
   </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">frame</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-null? 
          </span><span class="opn">(</span><span class="pln">qeval </span><span class="opn">(</span><span class="pln">negated-query operands</span><span class="clo">)</span><span class="pln">
                 </span><span class="opn">(</span><span class="pln">singleton-stream frame</span><span class="clo">)))</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">singleton-stream frame</span><span class="clo">)</span><span class="pln">
         the-empty-stream</span><span class="clo">))</span><span class="pln">
   frame-stream</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">put </span><span class="lit">'not</span><span class="pln"> </span><span class="lit">'qeval</span><span class="pln"> negate</span><span class="clo">)</span></pre></div>

<p><code>Lisp-value</code> is a filter similar to <code>not</code>.  Each frame in the stream
is used to instantiate the variables in the pattern, the indicated predicate is
applied, and the frames for which the predicate returns false are filtered out
of the input stream.  An error results if there are unbound pattern variables.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">lisp-value call frame-stream</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">stream-flatmap
   </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">frame</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">execute
          </span><span class="opn">(</span><span class="pln">instantiate
           call
           frame
           </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">v f</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="err">error</span><span class="pln"> 
              </span><span class="str">"Unknown pat var: LISP-VALUE"</span><span class="pln"> 
              v</span><span class="clo">))))</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">singleton-stream frame</span><span class="clo">)</span><span class="pln">
         the-empty-stream</span><span class="clo">))</span><span class="pln">
   frame-stream</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">put </span><span class="lit">'lisp-value</span><span class="pln"> </span><span class="lit">'qeval</span><span class="pln"> lisp-value</span><span class="clo">)</span></pre></div>

<p><code>Execute</code>, which applies the predicate to the arguments, must <code>eval</code>
the predicate expression to get the procedure to apply.  However, it must not
evaluate the arguments, since they are already the actual arguments, not
expressions whose evaluation (in Lisp) will produce the arguments.  Note that
<code>execute</code> is implemented using <code>eval</code> and <code>apply</code> from the
underlying Lisp system.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">execute exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">apply </span><span class="opn">(</span><span class="pln">eval </span><span class="opn">(</span><span class="pln">predicate exp</span><span class="clo">)</span><span class="pln"> 
               user-initial-environment</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">args exp</span><span class="clo">)))</span></pre></div>

<p>The <code>always-true</code> special form provides for a query that is always
satisfied.  It ignores its contents (normally empty) and simply passes through
all the frames in the input stream.  <code>Always-true</code> is used by the
<code>rule-body</code> selector (<a href="#g_t4_002e4_002e4_002e7">4.4.4.7</a>) to provide bodies for rules
that were defined without bodies (that is, rules whose conclusions are always
satisfied).
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">always-true ignore frame-stream</span><span class="clo">)</span><span class="pln"> 
  frame-stream</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">put </span><span class="lit">'always-true</span><span class="pln"> </span><span class="lit">'qeval</span><span class="pln"> always-true</span><span class="clo">)</span></pre></div>

<p>The selectors that define the syntax of <code>not</code> and <code>lisp-value</code> are
given in <a href="#g_t4_002e4_002e4_002e7">4.4.4.7</a>.
</p>
<a id="g_t4_002e4_002e4_002e3"></a>
<a id="Finding-Assertions-by-Pattern-Matching"></a>
<h5 class="subsubsection"><span class="secnum">4.4.4.3</span><span class="sectitle">Finding Assertions by Pattern Matching</span></h5>

<p><code>Find-assertions</code>, called by <code>simple-query</code> (<a href="#g_t4_002e4_002e4_002e2">4.4.4.2</a>),
takes as input a pattern and a frame.  It returns a stream of frames, each
extending the given one by a data-base match of the given pattern.  It uses
<code>fetch-assertions</code> (<a href="#g_t4_002e4_002e4_002e5">4.4.4.5</a>) to get a stream of all the
assertions in the data base that should be checked for a match against the
pattern and the frame.  The reason for <code>fetch-assertions</code> here is that we
can often apply simple tests that will eliminate many of the entries in the
data base from the pool of candidates for a successful match.  The system would
still work if we eliminated <code>fetch-assertions</code> and simply checked a stream
of all assertions in the data base, but the computation would be less efficient
because we would need to make many more calls to the matcher.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">find-assertions pattern frame</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">stream-flatmap 
    </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">datum</span><span class="clo">)</span><span class="pln"> 
      </span><span class="opn">(</span><span class="pln">check-an-assertion datum pattern frame</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">fetch-assertions pattern frame</span><span class="clo">)))</span></pre></div>

<p><code>Check-an-assertion</code> takes as arguments a pattern, a data object
(assertion), and a frame and returns either a one-element stream containing the
extended frame or <code>the-empty-stream</code> if the match fails.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">check-an-assertion 
         assertion query-pat query-frame</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">match-result
         </span><span class="opn">(</span><span class="pln">pattern-match 
          query-pat assertion query-frame</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> match-result </span><span class="lit">'failed</span><span class="clo">)</span><span class="pln">
        the-empty-stream
        </span><span class="opn">(</span><span class="pln">singleton-stream match-result</span><span class="clo">))))</span></pre></div>

<p>The basic pattern matcher returns either the symbol <code>failed</code> or an
extension of the given frame.  The basic idea of the matcher is to check the
pattern against the data, element by element, accumulating bindings for the
pattern variables.  If the pattern and the data object are the same, the match
succeeds and we return the frame of bindings accumulated so far.  Otherwise, if
the pattern is a variable we extend the current frame by binding the variable
to the data, so long as this is consistent with the bindings already in the
frame.  If the pattern and the data are both pairs, we (recursively) match the
<code>car</code> of the pattern against the <code>car</code> of the data to produce a
frame; in this frame we then match the <code>cdr</code> of the pattern against the
<code>cdr</code> of the data.  If none of these cases are applicable, the match fails
and we return the symbol <code>failed</code>.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pattern-match pat dat frame</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> frame </span><span class="lit">'failed</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'failed</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">equal</span><span class="pun">?</span><span class="pln"> pat dat</span><span class="clo">)</span><span class="pln"> frame</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">var? pat</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">extend-if-consistent 
          pat dat frame</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pair? pat</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pair? dat</span><span class="clo">))</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">pattern-match 
          </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> pat</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> dat</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">pattern-match
           </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> pat</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> dat</span><span class="clo">)</span><span class="pln"> frame</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="lit">'failed</span><span class="clo">)))</span></pre></div>

<p>Here is the procedure that extends a frame by adding a new binding, if this is
consistent with the bindings already in the frame:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">extend-if-consistent var dat frame</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">binding </span><span class="opn">(</span><span class="pln">binding-in-frame var frame</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> binding
        </span><span class="opn">(</span><span class="pln">pattern-match 
         </span><span class="opn">(</span><span class="pln">binding-value binding</span><span class="clo">)</span><span class="pln"> dat frame</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">extend var dat frame</span><span class="clo">))))</span></pre></div>

<p>If there is no binding for the variable in the frame, we simply add the binding
of the variable to the data.  Otherwise we match, in the frame, the data
against the value of the variable in the frame.  If the stored value contains
only constants, as it must if it was stored during pattern matching by
<code>extend-if-consistent</code>, then the match simply tests whether the stored and
new values are the same.  If so, it returns the unmodified frame; if not, it
returns a failure indication.  The stored value may, however, contain pattern
variables if it was stored during unification (see <a href="#g_t4_002e4_002e4_002e4">4.4.4.4</a>).  The
recursive match of the stored pattern against the new data will add or check
bindings for the variables in this pattern.  For example, suppose we have a
frame in which <code>?x</code> is bound to <code>(f ?y)</code> and <code>?y</code> is unbound,
and we wish to augment this frame by a binding of <code>?x</code> to <code>(f b)</code>.
We look up <code>?x</code> and find that it is bound to <code>(f ?y)</code>.  This leads us
to match <code>(f ?y)</code> against the proposed new value <code>(f b)</code> in the same
frame.  Eventually this match extends the frame by adding a binding of
<code>?y</code> to <code>b</code>.  <code>?X</code> remains bound to <code>(f ?y)</code>.  We never
modify a stored binding and we never store more than one binding for a given
variable.
</p>
<p>The procedures used by <code>extend-if-consistent</code> to manipulate bindings are
defined in <a href="#g_t4_002e4_002e4_002e8">4.4.4.8</a>.
</p>
<a id="Patterns-with-dotted-tails"></a>
<h5 class="subsubheading">Patterns with dotted tails</h5>

<p>If a pattern contains a dot followed by a pattern variable, the pattern
variable matches the rest of the data list (rather than the next element of the
data list), just as one would expect with the dotted-tail notation described in
<a href="2_002e2.xhtml#Exercise-2_002e20">Exercise 2.20</a>.  Although the pattern matcher we have just implemented
doesn’t look for dots, it does behave as we want.  This is because the Lisp
<code>read</code> primitive, which is used by <code>query-driver-loop</code> to read the
query and represent it as a list structure, treats dots in a special way.
</p>
<p>When <code>read</code> sees a dot, instead of making the next item be the next
element of a list (the <code>car</code> of a <code>cons</code> whose <code>cdr</code> will be the
rest of the list) it makes the next item be the <code>cdr</code> of the list
structure.  For example, the list structure produced by <code>read</code> for the
pattern <code>(computer ?type)</code> could be constructed by evaluating the
expression <code>(cons 'computer (cons '?type '()))</code>, and that for
<code>(computer . ?type)</code> could be constructed by evaluating the expression
<code>(cons 'computer '?type)</code>.
</p>
<p>Thus, as <code>pattern-match</code> recursively compares <code>car</code>s and <code>cdr</code>s
of a data list and a pattern that had a dot, it eventually matches the variable
after the dot (which is a <code>cdr</code> of the pattern) against a sublist of the
data list, binding the variable to that list.  For example, matching the
pattern <code>(computer . ?type)</code> against <code>(computer programmer trainee)</code>
will match <code>?type</code> against the list <code>(programmer trainee)</code>.
</p>
<a id="g_t4_002e4_002e4_002e4"></a>
<a id="Rules-and-Unification"></a>
<h5 class="subsubsection"><span class="secnum">4.4.4.4</span><span class="sectitle">Rules and Unification</span></h5>

<p><code>Apply-rules</code> is the rule analog of <code>find-assertions</code> 
(<a href="#g_t4_002e4_002e4_002e3">4.4.4.3</a>).  It takes as input a pattern and a frame, and it forms a stream
of extension frames by applying rules from the data base.
<code>Stream-flatmap</code> maps <code>apply-a-rule</code> down the stream of possibly
applicable rules (selected by <code>fetch-rules</code>, <a href="#g_t4_002e4_002e4_002e5">4.4.4.5</a>) and
combines the resulting streams of frames.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">apply-rules pattern frame</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">stream-flatmap 
   </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">rule</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">apply-a-rule rule pattern frame</span><span class="clo">))</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">fetch-rules pattern frame</span><span class="clo">)))</span></pre></div>

<p><code>Apply-a-rule</code> applies rules using the method outlined in 
<a href="#g_t4_002e4_002e2">4.4.2</a>.  It first augments its argument frame by unifying the rule
conclusion with the pattern in the given frame.  If this succeeds, it evaluates
the rule body in this new frame.
</p>
<p>Before any of this happens, however, the program renames all the variables in
the rule with unique new names.  The reason for this is to prevent the
variables for different rule applications from becoming confused with each
other.  For instance, if two rules both use a variable named <code>?x</code>, then
each one may add a binding for <code>?x</code> to the frame when it is applied.
These two <code>?x</code>’s have nothing to do with each other, and we should not be
fooled into thinking that the two bindings must be consistent.  Rather than
rename variables, we could devise a more clever environment structure; however,
the renaming approach we have chosen here is the most straightforward, even if
not the most efficient.  (See <a href="#Exercise-4_002e79">Exercise 4.79</a>.)  Here is the
<code>apply-a-rule</code> procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">apply-a-rule rule
                      query-pattern
                      query-frame</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">clean-rule 
         </span><span class="opn">(</span><span class="pln">rename-variables-in rule</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">unify-result
           </span><span class="opn">(</span><span class="pln">unify-match query-pattern
                        </span><span class="opn">(</span><span class="pln">conclusion clean-rule</span><span class="clo">)</span><span class="pln">
                        query-frame</span><span class="clo">)))</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> unify-result </span><span class="lit">'failed</span><span class="clo">)</span><span class="pln">
          the-empty-stream
          </span><span class="opn">(</span><span class="pln">qeval </span><span class="opn">(</span><span class="pln">rule-body clean-rule</span><span class="clo">)</span><span class="pln">
                 </span><span class="opn">(</span><span class="pln">singleton-stream 
                  unify-result</span><span class="clo">))))))</span></pre></div>

<p>The selectors <code>rule-body</code> and <code>conclusion</code> that extract parts of a
rule are defined in <a href="#g_t4_002e4_002e4_002e7">4.4.4.7</a>.
</p>
<p>We generate unique variable names by associating a unique identifier (such as a
number) with each rule application and combining this identifier with the
original variable names.  For example, if the rule-application identifier is 7,
we might change each <code>?x</code> in the rule to <code>?x-7</code> and each <code>?y</code> in
the rule to <code>?y-7</code>.  (<code>Make-new-variable</code> and
<code>new-rule-application-id</code> are included with the syntax procedures in
<a href="#g_t4_002e4_002e4_002e7">4.4.4.7</a>.)
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">rename-variables-in rule</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">rule-application-id 
         </span><span class="opn">(</span><span class="pln">new-rule-application-id</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">tree-walk exp</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">var? exp</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">make-new-variable 
              exp 
              rule-application-id</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">((</span><span class="pln">pair? exp</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="pln">tree-walk </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> exp</span><span class="clo">))</span><span class="pln">
                   </span><span class="opn">(</span><span class="pln">tree-walk </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> exp</span><span class="clo">))))</span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> exp</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">tree-walk rule</span><span class="clo">)))</span></pre></div>

<p>The unification algorithm is implemented as a procedure that takes as inputs
two patterns and a frame and returns either the extended frame or the symbol
<code>failed</code>.  The unifier is like the pattern matcher except that it is
symmetrical—variables are allowed on both sides of the match.
<code>Unify-match</code> is basically the same as <code>pattern-match</code>, except that
there is extra code (marked “<code>***</code>” below) to handle the case where the
object on the right side of the match is a variable.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">unify-match p1 p2 frame</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> frame </span><span class="lit">'failed</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'failed</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">equal</span><span class="pun">?</span><span class="pln"> p1 p2</span><span class="clo">)</span><span class="pln"> frame</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">var? p1</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">extend-if-possible p1 p2 frame</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">var? p2</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">extend-if-possible 
          p2 
          p1 
          frame</span><span class="clo">))</span><span class="pln">        </span><span class="com">; </span><span class="roman"><span class="com">***</span></span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pair? p1</span><span class="clo">)</span><span class="pln"> 
              </span><span class="opn">(</span><span class="pln">pair? p2</span><span class="clo">))</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">unify-match 
          </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> p1</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> p2</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">unify-match 
           </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> p1</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> p2</span><span class="clo">)</span><span class="pln">
           frame</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="lit">'failed</span><span class="clo">)))</span></pre></div>

<p>In unification, as in one-sided pattern matching, we want to accept a proposed
extension of the frame only if it is consistent with existing bindings.  The
procedure <code>extend-if-possible</code> used in unification is the same as the
<code>extend-if-consistent</code> used in pattern matching except for two special
checks, marked “<code>***</code>” in the program below.  In the first case, if the
variable we are trying to match is not bound, but the value we are trying to
match it with is itself a (different) variable, it is necessary to check to see
if the value is bound, and if so, to match its value.  If both parties to the
match are unbound, we may bind either to the other.
</p>
<p>The second check deals with attempts to bind a variable to a pattern that
includes that variable.  Such a situation can occur whenever a variable is
repeated in both patterns.  Consider, for example, unifying the two patterns
<code>(?x ?x)</code> and <code>(?y ⟨<var>expression involving <code>?y</code></var>⟩)</code> in a
frame where both <code>?x</code> and <code>?y</code> are unbound.  First <code>?x</code> is
matched against <code>?y</code>, making a binding of <code>?x</code> to <code>?y</code>.  Next,
the same <code>?x</code> is matched against the given expression involving <code>?y</code>.
Since <code>?x</code> is already bound to <code>?y</code>, this results in matching
<code>?y</code> against the expression.  If we think of the unifier as finding a set
of values for the pattern variables that make the patterns the same, then these
patterns imply instructions to find a <code>?y</code> such that <code>?y</code> is equal to
the expression involving <code>?y</code>.  There is no general method for solving
such equations, so we reject such bindings; these cases are recognized by the
predicate <code>depends-on?</code>.<a class="footnote_link" id="DOCF284" href="#FOOT284"><sup>284</sup></a>  On the
other hand, we do not want to reject attempts to bind a variable to itself.
For example, consider unifying <code>(?x ?x)</code> and <code>(?y ?y)</code>.  The second
attempt to bind <code>?x</code> to <code>?y</code> matches <code>?y</code> (the stored value of
<code>?x</code>) against <code>?y</code> (the new value of <code>?x</code>).  This is taken care
of by the <code>equal?</code>  clause of <code>unify-match</code>.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">extend-if-possible var val frame</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">binding </span><span class="opn">(</span><span class="pln">binding-in-frame var frame</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">(</span><span class="pln">binding
           </span><span class="opn">(</span><span class="pln">unify-match
            </span><span class="opn">(</span><span class="pln">binding-value binding</span><span class="clo">)</span><span class="pln"> val frame</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">((</span><span class="pln">var? val</span><span class="clo">)</span><span class="pln">                   </span><span class="roman"><span class="com">; ***</span></span><span class="pln">
           </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">binding 
                  </span><span class="opn">(</span><span class="pln">binding-in-frame 
                   val
                   frame</span><span class="clo">)))</span><span class="pln">
             </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> binding
                 </span><span class="opn">(</span><span class="pln">unify-match
                  var 
                  </span><span class="opn">(</span><span class="pln">binding-value binding</span><span class="clo">)</span><span class="pln"> 
                  frame</span><span class="clo">)</span><span class="pln">
                 </span><span class="opn">(</span><span class="pln">extend var val frame</span><span class="clo">))))</span><span class="pln">
          </span><span class="opn">((</span><span class="pln">depends-on? val var frame</span><span class="clo">)</span><span class="pln">  </span><span class="roman"><span class="com">; ***</span></span><span class="pln">
           </span><span class="lit">'failed</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="pln">extend var val frame</span><span class="clo">)))))</span></pre></div>

<p><code>Depends-on?</code> is a predicate that tests whether an expression proposed to
be the value of a pattern variable depends on the variable.  This must be done
relative to the current frame because the expression may contain occurrences of
a variable that already has a value that depends on our test variable.  The
structure of <code>depends-on?</code> is a simple recursive tree walk in which we
substitute for the values of variables whenever necessary.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">depends-on? exp var frame</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">tree-walk e</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">var? e</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">equal</span><span class="pun">?</span><span class="pln"> var e</span><span class="clo">)</span><span class="pln">
               true
               </span><span class="opn">(</span><span class="kwd">let</span><span class="pln">
                 </span><span class="opn">((</span><span class="pln">b </span><span class="opn">(</span><span class="pln">binding-in-frame 
                      e 
                      frame</span><span class="clo">)))</span><span class="pln">
                  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> b
                      </span><span class="opn">(</span><span class="pln">tree-walk 
                       </span><span class="opn">(</span><span class="pln">binding-value b</span><span class="clo">))</span><span class="pln">
                      false</span><span class="clo">))))</span><span class="pln">
          </span><span class="opn">((</span><span class="pln">pair? e</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="kwd">or</span><span class="pln"> </span><span class="opn">(</span><span class="pln">tree-walk </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> e</span><span class="clo">))</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">tree-walk </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> e</span><span class="clo">))))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> false</span><span class="clo">)))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">tree-walk exp</span><span class="clo">))</span></pre></div>

<a id="g_t4_002e4_002e4_002e5"></a>
<a id="Maintaining-the-Data-Base"></a>
<h5 class="subsubsection"><span class="secnum">4.4.4.5</span><span class="sectitle">Maintaining the Data Base</span></h5>

<p>One important problem in designing logic programming languages is that of
arranging things so that as few irrelevant data-base entries as possible will
be examined in checking a given pattern.  In our system, in addition to storing
all assertions in one big stream, we store all assertions whose <code>car</code>s are
constant symbols in separate streams, in a table indexed by the symbol.  To
fetch an assertion that may match a pattern, we first check to see if the
<code>car</code> of the pattern is a constant symbol.  If so, we return (to be tested
using the matcher) all the stored assertions that have the same <code>car</code>.  If
the pattern’s <code>car</code> is not a constant symbol, we return all the stored
assertions.  Cleverer methods could also take advantage of information in the
frame, or try also to optimize the case where the <code>car</code> of the pattern is
not a constant symbol.  We avoid building our criteria for indexing (using the
<code>car</code>, handling only the case of constant symbols) into the program;
instead we call on predicates and selectors that embody our criteria.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> THE-ASSERTIONS the-empty-stream</span><span class="clo">)</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fetch-assertions pattern frame</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">use-index? pattern</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">get-indexed-assertions pattern</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">get-all-assertions</span><span class="clo">)))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">get-all-assertions</span><span class="clo">)</span><span class="pln"> THE-ASSERTIONS</span><span class="clo">)</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">get-indexed-assertions pattern</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">get-stream </span><span class="opn">(</span><span class="pln">index-key-of pattern</span><span class="clo">)</span><span class="pln">
              </span><span class="lit">'assertion-stream</span><span class="clo">))</span></pre></div>

<p><code>Get-stream</code> looks up a stream in the table and returns an empty stream if
nothing is stored there.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">get-stream key1 key2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">s </span><span class="opn">(</span><span class="pln">get key1 key2</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> s s the-empty-stream</span><span class="clo">)))</span></pre></div>

<p>Rules are stored similarly, using the <code>car</code> of the rule conclusion.  Rule
conclusions are arbitrary patterns, however, so they differ from assertions in
that they can contain variables.  A pattern whose <code>car</code> is a constant
symbol can match rules whose conclusions start with a variable as well as rules
whose conclusions have the same <code>car</code>.  Thus, when fetching rules that
might match a pattern whose <code>car</code> is a constant symbol we fetch all rules
whose conclusions start with a variable as well as those whose conclusions have
the same <code>car</code> as the pattern.  For this purpose we store all rules whose
conclusions start with a variable in a separate stream in our table, indexed by
the symbol <code>?</code>.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> THE-RULES the-empty-stream</span><span class="clo">)</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fetch-rules pattern frame</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">use-index? pattern</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">get-indexed-rules pattern</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">get-all-rules</span><span class="clo">)))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">get-all-rules</span><span class="clo">)</span><span class="pln"> THE-RULES</span><span class="clo">)</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">get-indexed-rules pattern</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">stream-append
   </span><span class="opn">(</span><span class="pln">get-stream </span><span class="opn">(</span><span class="pln">index-key-of pattern</span><span class="clo">)</span><span class="pln">
               </span><span class="lit">'rule-stream</span><span class="clo">)</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">get-stream </span><span class="lit">'</span><span class="pun">?</span><span class="pln"> </span><span class="lit">'rule-stream</span><span class="clo">)))</span></pre></div>

<p><code>Add-rule-or-assertion!</code> is used by <code>query-driver-loop</code> to add
assertions and rules to the data base.  Each item is stored in the index, if
appropriate, and in a stream of all assertions or rules in the data base.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">add-rule-or-assertion! assertion</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">rule? assertion</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">add-rule! assertion</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">add-assertion! assertion</span><span class="clo">)))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">add-assertion! assertion</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">store-assertion-in-index assertion</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">old-assertions THE-ASSERTIONS</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> THE-ASSERTIONS
          </span><span class="opn">(</span><span class="pln">cons-stream assertion 
                       old-assertions</span><span class="clo">))</span><span class="pln">
    </span><span class="lit">'ok</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">add-rule! rule</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">store-rule-in-index rule</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">old-rules THE-RULES</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> THE-RULES
          </span><span class="opn">(</span><span class="pln">cons-stream rule old-rules</span><span class="clo">))</span><span class="pln">
    </span><span class="lit">'ok</span><span class="clo">))</span></pre></div>

<p>To actually store an assertion or a rule, we check to see if it can be indexed.
If so, we store it in the appropriate stream.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">store-assertion-in-index assertion</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">indexable? assertion</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">key </span><span class="opn">(</span><span class="pln">index-key-of assertion</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">current-assertion-stream
               </span><span class="opn">(</span><span class="pln">get-stream 
                key </span><span class="lit">'assertion-stream</span><span class="clo">)))</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">put key
               </span><span class="lit">'assertion-stream</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">cons-stream 
                assertion
                current-assertion-stream</span><span class="clo">))))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">store-rule-in-index rule</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">pattern </span><span class="opn">(</span><span class="pln">conclusion rule</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">indexable? pattern</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">key </span><span class="opn">(</span><span class="pln">index-key-of pattern</span><span class="clo">)))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">current-rule-stream
                 </span><span class="opn">(</span><span class="pln">get-stream 
                  key </span><span class="lit">'rule-stream</span><span class="clo">)))</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">put key
                 </span><span class="lit">'rule-stream</span><span class="pln">
                 </span><span class="opn">(</span><span class="pln">cons-stream 
                  rule
                  current-rule-stream</span><span class="clo">)))))))</span></pre></div>

<p>The following procedures define how the data-base index is used.  A pattern (an
assertion or a rule conclusion) will be stored in the table if it starts with a
variable or a constant symbol.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">indexable? pat</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">or</span><span class="pln"> </span><span class="opn">(</span><span class="pln">constant-symbol? </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> pat</span><span class="clo">))</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">var? </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> pat</span><span class="clo">))))</span></pre></div>

<p>The key under which a pattern is stored in the table is either <code>?</code> (if it
starts with a variable) or the constant symbol with which it starts.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">index-key-of pat</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">key </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> pat</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">var? key</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'</span><span class="pun">?</span><span class="pln"> key</span><span class="clo">)))</span></pre></div>

<p>The index will be used to retrieve items that might match a pattern if the
pattern starts with a constant symbol.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">use-index? pat</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">constant-symbol? </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> pat</span><span class="clo">)))</span></pre></div>

<blockquote>
<p><strong><a id="Exercise-4_002e70"></a>Exercise 4.70:</strong> What is the purpose of the
<code>let</code> bindings in the procedures <code>add-assertion!</code> and
<code>add-rule!</code>?  What would be wrong with the following implementation of
<code>add-assertion!</code>?  Hint: Recall the definition of the infinite stream of
ones in <a href="3_002e5.xhtml#g_t3_002e5_002e2">3.5.2</a>: <code>(define ones (cons-stream 1 ones))</code>.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">add-assertion! assertion</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">store-assertion-in-index assertion</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> THE-ASSERTIONS
        </span><span class="opn">(</span><span class="pln">cons-stream assertion 
                     THE-ASSERTIONS</span><span class="clo">))</span><span class="pln">
  </span><span class="lit">'ok</span><span class="clo">)</span></pre></div>
</blockquote>

<a id="g_t4_002e4_002e4_002e6"></a>
<a id="Stream-Operations"></a>
<h5 class="subsubsection"><span class="secnum">4.4.4.6</span><span class="sectitle">Stream Operations</span></h5>

<p>The query system uses a few stream operations that were not presented in
<a href="Chapter-3.xhtml#Chapter-3">Chapter 3</a>.
</p>
<p><code>Stream-append-delayed</code> and <code>interleave-delayed</code> are just like
<code>stream-append</code> and <code>interleave</code> (<a href="3_002e5.xhtml#g_t3_002e5_002e3">3.5.3</a>), except that
they take a delayed argument (like the <code>integral</code> procedure in 
<a href="3_002e5.xhtml#g_t3_002e5_002e4">3.5.4</a>).  This postpones looping in some cases (see <a href="#Exercise-4_002e71">Exercise 4.71</a>).
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-append-delayed s1 delayed-s2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-null? s1</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">force delayed-s2</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">cons-stream
       </span><span class="opn">(</span><span class="pln">stream-car s1</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">stream-append-delayed </span><span class="opn">(</span><span class="pln">stream-cdr s1</span><span class="clo">)</span><span class="pln">
                              delayed-s2</span><span class="clo">))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">interleave-delayed s1 delayed-s2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-null? s1</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">force delayed-s2</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">cons-stream
       </span><span class="opn">(</span><span class="pln">stream-car s1</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">interleave-delayed 
        </span><span class="opn">(</span><span class="pln">force delayed-s2</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">delay</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-cdr s1</span><span class="clo">))))))</span></pre></div>

<p><code>Stream-flatmap</code>, which is used throughout the query evaluator to map a
procedure over a stream of frames and combine the resulting streams of frames,
is the stream analog of the <code>flatmap</code> procedure introduced for ordinary
lists in <a href="2_002e2.xhtml#g_t2_002e2_002e3">2.2.3</a>.  Unlike ordinary <code>flatmap</code>, however, we
accumulate the streams with an interleaving process, rather than simply
appending them (see <a href="#Exercise-4_002e72">Exercise 4.72</a> and <a href="#Exercise-4_002e73">Exercise 4.73</a>).
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-flatmap proc s</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">flatten-stream </span><span class="opn">(</span><span class="pln">stream-map proc s</span><span class="clo">)))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">flatten-stream stream</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-null? stream</span><span class="clo">)</span><span class="pln">
      the-empty-stream
      </span><span class="opn">(</span><span class="pln">interleave-delayed
       </span><span class="opn">(</span><span class="pln">stream-car stream</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="kwd">delay</span><span class="pln"> </span><span class="opn">(</span><span class="pln">flatten-stream
               </span><span class="opn">(</span><span class="pln">stream-cdr stream</span><span class="clo">))))))</span></pre></div>

<p>The evaluator also uses the following simple procedure to generate a stream
consisting of a single element:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">singleton-stream x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">cons-stream x the-empty-stream</span><span class="clo">))</span></pre></div>

<a id="g_t4_002e4_002e4_002e7"></a>
<a id="Query-Syntax-Procedures"></a>
<h5 class="subsubsection"><span class="secnum">4.4.4.7</span><span class="sectitle">Query Syntax Procedures</span></h5>

<p><code>Type</code> and <code>contents</code>, used by <code>qeval</code> (<a href="#g_t4_002e4_002e4_002e2">4.4.4.2</a>),
specify that a special form is identified by the symbol in its <code>car</code>.
They are the same as the <code>type-tag</code> and <code>contents</code> procedures in
<a href="2_002e4.xhtml#g_t2_002e4_002e2">2.4.2</a>, except for the error message.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">type exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pair? exp</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> exp</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown expression TYPE"</span><span class="pln">
             exp</span><span class="clo">)))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">contents exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pair? exp</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> exp</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown expression CONTENTS"</span><span class="pln">
             exp</span><span class="clo">)))</span></pre></div>

<p>The following procedures, used by <code>query-driver-loop</code> (in 
<a href="#g_t4_002e4_002e4_002e1">4.4.4.1</a>), specify that rules and assertions are added to the data base by
expressions of the form <code>(assert! ⟨<var>rule-or-assertion</var>⟩)</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">assertion-to-be-added? exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> </span><span class="opn">(</span><span class="pln">type exp</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'assert!</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">add-assertion-body exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> </span><span class="opn">(</span><span class="pln">contents exp</span><span class="clo">)))</span></pre></div>

<p>Here are the syntax definitions for the <code>and</code>, <code>or</code>, <code>not</code>, and
<code>lisp-value</code> special forms (<a href="#g_t4_002e4_002e4_002e2">4.4.4.2</a>):
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">empty-conjunction? exps</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? exps</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">first-conjunct exps</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> exps</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">rest-conjuncts exps</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> exps</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">empty-disjunction? exps</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? exps</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">first-disjunct exps</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> exps</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">rest-disjuncts exps</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> exps</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">negated-query exps</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> exps</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">predicate exps</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> exps</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">args exps</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> exps</span><span class="clo">))</span></pre></div>

<p>The following three procedures define the syntax of rules:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">rule? statement</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">tagged-list? statement </span><span class="lit">'rule</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">conclusion rule</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> rule</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">rule-body rule</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? </span><span class="opn">(</span><span class="kwd">cddr</span><span class="pln"> rule</span><span class="clo">))</span><span class="pln">
      </span><span class="lit">'</span><span class="opn">(</span><span class="pln">always-true</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">caddr</span><span class="pln"> rule</span><span class="clo">)))</span></pre></div>

<p><code>Query-driver-loop</code> (<a href="#g_t4_002e4_002e4_002e1">4.4.4.1</a>) calls
<code>query-syntax-process</code> to transform pattern variables in the expression,
which have the form <code>?symbol</code>, into the internal format <code>(? symbol)</code>.
That is to say, a pattern such as <code>(job ?x ?y)</code> is actually represented
internally by the system as <code>(job (? x) (? y))</code>.  This increases the
efficiency of query processing, since it means that the system can check to see
if an expression is a pattern variable by checking whether the <code>car</code> of
the expression is the symbol <code>?</code>, rather than having to extract characters
from the symbol.  The syntax transformation is accomplished by the following
procedure:<a class="footnote_link" id="DOCF285" href="#FOOT285"><sup>285</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">query-syntax-process exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">map-over-symbols expand-question-mark exp</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">map-over-symbols proc exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">pair? exp</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="pln">map-over-symbols 
                proc </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> exp</span><span class="clo">))</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">map-over-symbols 
                proc </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> exp</span><span class="clo">))))</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">symbol? exp</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">proc exp</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> exp</span><span class="clo">)))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">expand-question-mark symbol</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">chars </span><span class="opn">(</span><span class="pln">symbol-</span><span class="pun">&gt;</span><span class="pln">string symbol</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">string=</span><span class="pun">?</span><span class="pln"> </span><span class="opn">(</span><span class="pln">substring chars </span><span class="lit">0</span><span class="pln"> </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> </span><span class="str">"?"</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'</span><span class="pun">?</span><span class="pln"> </span><span class="opn">(</span><span class="pln">string-</span><span class="pun">&gt;</span><span class="pln">symbol
                  </span><span class="opn">(</span><span class="pln">substring
                   chars 
                   </span><span class="lit">1</span><span class="pln"> 
                   </span><span class="opn">(</span><span class="pln">string-length chars</span><span class="clo">))))</span><span class="pln">
        symbol</span><span class="clo">)))</span></pre></div>

<p>Once the variables are transformed in this way, the variables in a pattern are
lists starting with <code>?</code>, and the constant symbols (which need to be
recognized for data-base indexing, <a href="#g_t4_002e4_002e4_002e5">4.4.4.5</a>) are just the symbols.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">var? exp</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">tagged-list? exp </span><span class="lit">'</span><span class="pun">?</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">constant-symbol? exp</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">symbol? exp</span><span class="clo">))</span></pre></div>

<p>Unique variables are constructed during rule application (in 
<a href="#g_t4_002e4_002e4_002e4">4.4.4.4</a>) by means of the following procedures.  The unique identifier for
a rule application is a number, which is incremented each time a rule is
applied.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> rule-counter </span><span class="lit">0</span><span class="clo">)</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">new-rule-application-id</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> rule-counter </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> rule-counter</span><span class="clo">))</span><span class="pln">
  rule-counter</span><span class="clo">)</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-new-variable 
         var rule-application-id</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="lit">'</span><span class="pun">?</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> rule-application-id
                 </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> var</span><span class="clo">))))</span></pre></div>

<p>When <code>query-driver-loop</code> instantiates the query to print the answer, it
converts any unbound pattern variables back to the right form for printing,
using
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">contract-question-mark variable</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">string-</span><span class="pun">&gt;</span><span class="pln">symbol
   </span><span class="opn">(</span><span class="pln">string-append </span><span class="str">"?"</span><span class="pln">
     </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">number? </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> variable</span><span class="clo">))</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">string-append
          </span><span class="opn">(</span><span class="pln">symbol-</span><span class="pun">&gt;</span><span class="pln">string </span><span class="opn">(</span><span class="kwd">caddr</span><span class="pln"> variable</span><span class="clo">))</span><span class="pln">
          </span><span class="str">"-"</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">number-</span><span class="pun">&gt;</span><span class="pln">string </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> variable</span><span class="clo">)))</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">symbol-</span><span class="pun">&gt;</span><span class="pln">string </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> variable</span><span class="clo">))))))</span></pre></div>

<a id="g_t4_002e4_002e4_002e8"></a>
<a id="Frames-and-Bindings"></a>
<h5 class="subsubsection"><span class="secnum">4.4.4.8</span><span class="sectitle">Frames and Bindings</span></h5>

<p>Frames are represented as lists of bindings, which are variable-value pairs:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-binding variable value</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> variable value</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">binding-variable binding</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> binding</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">binding-value binding</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> binding</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">binding-in-frame variable frame</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assoc variable frame</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">extend variable value frame</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-binding variable value</span><span class="clo">)</span><span class="pln"> frame</span><span class="clo">))</span></pre></div>

<blockquote>
<p><strong><a id="Exercise-4_002e71"></a>Exercise 4.71:</strong> Louis Reasoner wonders why the
<code>simple-query</code> and <code>disjoin</code> procedures (<a href="#g_t4_002e4_002e4_002e2">4.4.4.2</a>) are
implemented using explicit <code>delay</code> operations, rather than being defined
as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">simple-query 
         query-pattern frame-stream</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">stream-flatmap
   </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">frame</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">stream-append
      </span><span class="opn">(</span><span class="pln">find-assertions query-pattern frame</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">apply-rules query-pattern frame</span><span class="clo">)))</span><span class="pln">
   frame-stream</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">disjoin disjuncts frame-stream</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">empty-disjunction? disjuncts</span><span class="clo">)</span><span class="pln">
      the-empty-stream
      </span><span class="opn">(</span><span class="pln">interleave
       </span><span class="opn">(</span><span class="pln">qeval </span><span class="opn">(</span><span class="pln">first-disjunct disjuncts</span><span class="clo">)</span><span class="pln">
              frame-stream</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">disjoin </span><span class="opn">(</span><span class="pln">rest-disjuncts disjuncts</span><span class="clo">)</span><span class="pln">
                frame-stream</span><span class="clo">))))</span></pre></div>

<p>Can you give examples of queries where these simpler definitions would lead to
undesirable behavior?
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e72"></a>Exercise 4.72:</strong> Why do <code>disjoin</code> and
<code>stream-flatmap</code> interleave the streams rather than simply append them?
Give examples that illustrate why interleaving works better.  (Hint: Why did we
use <code>interleave</code> in <a href="3_002e5.xhtml#g_t3_002e5_002e3">3.5.3</a>?)
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e73"></a>Exercise 4.73:</strong> Why does <code>flatten-stream</code>
use <code>delay</code> explicitly?  What would be wrong with defining it as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">flatten-stream stream</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-null? stream</span><span class="clo">)</span><span class="pln">
      the-empty-stream
      </span><span class="opn">(</span><span class="pln">interleave </span><span class="opn">(</span><span class="pln">stream-car stream</span><span class="clo">)</span><span class="pln">
                  </span><span class="opn">(</span><span class="pln">flatten-stream 
                   </span><span class="opn">(</span><span class="pln">stream-cdr stream</span><span class="clo">)))))</span></pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e74"></a>Exercise 4.74:</strong> Alyssa P. Hacker proposes to use
a simpler version of <code>stream-flatmap</code> in <code>negate</code>, <code>lisp-value</code>,
and <code>find-assertions</code>.  She observes that the procedure that is mapped
over the frame stream in these cases always produces either the empty stream or
a singleton stream, so no interleaving is needed when combining these streams.
</p>
<ol>
<li> Fill in the missing expressions in Alyssa’s program.

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">simple-stream-flatmap proc s</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">simple-flatten </span><span class="opn">(</span><span class="pln">stream-map proc s</span><span class="clo">)))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">simple-flatten stream</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">stream-map ⟨</span><span class="pun">??</span><span class="pln">⟩
              </span><span class="opn">(</span><span class="pln">stream-filter ⟨</span><span class="pun">??</span><span class="pln">⟩ 
                             stream</span><span class="clo">)))</span></pre></div>

</li><li> Does the query system’s behavior change if we change it in this way?

</li></ol>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e75"></a>Exercise 4.75:</strong> Implement for the query language
a new special form called <code>unique</code>.  <code>Unique</code> should succeed if there
is precisely one item in the data base satisfying a specified query.  For
example,
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">unique </span><span class="opn">(</span><span class="pln">job </span><span class="pun">?</span><span class="pln">x </span><span class="opn">(</span><span class="pln">computer wizard</span><span class="clo">)))</span></pre></div>

<p>should print the one-item stream
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">unique </span><span class="opn">(</span><span class="pln">job </span><span class="opn">(</span><span class="pln">Bitdiddle Ben</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">computer wizard</span><span class="clo">)))</span></pre></div>

<p>since Ben is the only computer wizard, and
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">unique </span><span class="opn">(</span><span class="pln">job </span><span class="pun">?</span><span class="pln">x </span><span class="opn">(</span><span class="pln">computer programmer</span><span class="clo">)))</span></pre></div>

<p>should print the empty stream, since there is more than one computer
programmer.  Moreover,
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">job </span><span class="pun">?</span><span class="pln">x </span><span class="pun">?</span><span class="pln">j</span><span class="clo">)</span><span class="pln"> 
     </span><span class="opn">(</span><span class="pln">unique </span><span class="opn">(</span><span class="pln">job </span><span class="pun">?</span><span class="pln">anyone </span><span class="pun">?</span><span class="pln">j</span><span class="clo">)))</span></pre></div>

<p>should list all the jobs that are filled by only one person, and the people who
fill them.
</p>
<p>There are two parts to implementing <code>unique</code>.  The first is to write a
procedure that handles this special form, and the second is to make
<code>qeval</code> dispatch to that procedure.  The second part is trivial, since
<code>qeval</code> does its dispatching in a data-directed way.  If your procedure is
called <code>uniquely-asserted</code>, all you need to do is
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">put </span><span class="lit">'unique</span><span class="pln"> </span><span class="lit">'qeval</span><span class="pln"> uniquely-asserted</span><span class="clo">)</span></pre></div>

<p>and <code>qeval</code> will dispatch to this procedure for every query whose
<code>type</code> (<code>car</code>) is the symbol <code>unique</code>.
</p>
<p>The real problem is to write the procedure <code>uniquely-asserted</code>.  This
should take as input the <code>contents</code> (<code>cdr</code>) of the <code>unique</code>
query, together with a stream of frames.  For each frame in the stream, it
should use <code>qeval</code> to find the stream of all extensions to the frame that
satisfy the given query.  Any stream that does not have exactly one item in it
should be eliminated.  The remaining streams should be passed back to be
accumulated into one big stream that is the result of the <code>unique</code> query.
This is similar to the implementation of the <code>not</code> special form.
</p>
<p>Test your implementation by forming a query that lists all people who supervise
precisely one person.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e76"></a>Exercise 4.76:</strong> Our implementation of <code>and</code>
as a series combination of queries (<a href="#Figure-4_002e5">Figure 4.5</a>) is elegant, but it is
inefficient because in processing the second query of the <code>and</code> we must
scan the data base for each frame produced by the first query.  If the data
base has <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> elements, and a typical query produces a number of output frames
proportional to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> (say <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mspace width="thinmathspace"/>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mspace width="thinmathspace"/>
    <mi>k</mi>
  </mrow>
</math>), then scanning the data base for each
frame produced by the first query will require <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msup>
      <mi>n</mi>
      <mn>2</mn>
    </msup>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mspace width="thinmathspace"/>
    <mi>k</mi>
  </mrow>
</math> calls to the
pattern matcher.  Another approach would be to process the two clauses of the
<code>and</code> separately, then look for all pairs of output frames that are
compatible.  If each query produces <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mspace width="thinmathspace"/>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mspace width="thinmathspace"/>
    <mi>k</mi>
  </mrow>
</math> output frames, then this means
that we must perform <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msup>
      <mi>n</mi>
      <mn>2</mn>
    </msup>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mspace width="thinmathspace"/>
    <msup>
      <mi>k</mi>
      <mn>2</mn>
    </msup>
  </mrow>
</math> compatibility checks—a factor of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>k</mi>
</math>
fewer than the number of matches required in our current method.
</p>
<p>Devise an implementation of <code>and</code> that uses this strategy.  You must
implement a procedure that takes two frames as inputs, checks whether the
bindings in the frames are compatible, and, if so, produces a frame that merges
the two sets of bindings.  This operation is similar to unification.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e77"></a>Exercise 4.77:</strong> In <a href="#g_t4_002e4_002e3">4.4.3</a> we saw
that <code>not</code> and <code>lisp-value</code> can cause the query language to give
“wrong” answers if these filtering operations are applied to frames in which
variables are unbound.  Devise a way to fix this shortcoming.  One idea is to
perform the filtering in a “delayed” manner by appending to the frame a
“promise” to filter that is fulfilled only when enough variables have been
bound to make the operation possible.  We could wait to perform filtering until
all other operations have been performed.  However, for efficiency’s sake, we
would like to perform filtering as soon as possible so as to cut down on the
number of intermediate frames generated.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e78"></a>Exercise 4.78:</strong> Redesign the query language as a
nondeterministic program to be implemented using the evaluator of 
<a href="4_002e3.xhtml#g_t4_002e3">4.3</a>, rather than as a stream process.  In this approach, each query will
produce a single answer (rather than the stream of all answers) and the user
can type <code>try-again</code> to see more answers.  You should find that much of
the mechanism we built in this section is subsumed by nondeterministic search
and backtracking.  You will probably also find, however, that your new query
language has subtle differences in behavior from the one implemented here.  Can
you find examples that illustrate this difference?
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-4_002e79"></a>Exercise 4.79:</strong> When we implemented the Lisp
evaluator in <a href="4_002e1.xhtml#g_t4_002e1">4.1</a>, we saw how to use local environments to avoid
name conflicts between the parameters of procedures.  For example, in
evaluating
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">square x</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x x</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sum-of-squares x y</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">square x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">square y</span><span class="clo">)))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">sum-of-squares </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="clo">)</span></pre></div>

<p>there is no confusion between the <code>x</code> in <code>square</code> and the <code>x</code> in
<code>sum-of-squares</code>, because we evaluate the body of each procedure in an
environment that is specially constructed to contain bindings for the local
variables.  In the query system, we used a different strategy to avoid name
conflicts in applying rules.  Each time we apply a rule we rename the variables
with new names that are guaranteed to be unique.  The analogous strategy for
the Lisp evaluator would be to do away with local environments and simply
rename the variables in the body of a procedure each time we apply the
procedure.
</p>
<p>Implement for the query language a rule-application method that uses
environments rather than renaming.  See if you can build on your environment
structure to create constructs in the query language for dealing with large
systems, such as the rule analog of block-structured procedures.  Can you
relate any of this to the problem of making deductions in a context (e.g., “If
I supposed that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>P</mi>
</math> were true, then I would be able to deduce <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>A</mi>
</math> and
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>B</mi>
</math>.”) as a method of problem solving?  (This problem is open-ended.  A good
answer is probably worth a Ph.D.)
</p></blockquote>

<div class="footnote">
<h4 class="footnotes-heading">Footnotes</h4>

<div id="FOOT262"><p><a class="footnote_backlink" href="#DOCF262"><sup>262</sup></a>
Logic
programming has grown out of a long history of research in automatic theorem
proving.  Early theorem-proving programs could accomplish very little, because
they exhaustively searched the space of possible proofs.  The major
breakthrough that made such a search plausible was the discovery in the early
1960s of the <a id="index-unification-algorithm"></a>
<em>unification algorithm</em> and the <a id="index-resolution-principle"></a>
<em>resolution principle</em> 
(<a href="References.xhtml#Robinson-1965">Robinson 1965</a>).  Resolution was used, for example, by 
<a href="References.xhtml#Green-and-Raphael-_00281968_0029">Green and Raphael (1968)</a> (see also <a href="References.xhtml#Green-1969">Green 1969</a>) as the basis for a deductive
question-answering system.  During most of this period, researchers
concentrated on algorithms that are guaranteed to find a proof if one exists.
Such algorithms were difficult to control and to direct toward a proof.  
<a href="References.xhtml#Hewitt-_00281969_0029">Hewitt (1969)</a> recognized the possibility of merging the control structure of a
programming language with the operations of a logic-manipulation system,
leading to the work in automatic search mentioned in <a href="4_002e3.xhtml#g_t4_002e3_002e1">4.3.1</a>
(<a href="4_002e3.xhtml#Footnote-250">Footnote 250</a>).  At the same time that this was being done,
Colmerauer, in Marseille, was developing rule-based systems for manipulating
natural language (see <a href="References.xhtml#Colmerauer-et-al_002e-1973">Colmerauer et al. 1973</a>).  He invented a programming
language called Prolog for representing those rules.  <a href="References.xhtml#Kowalski-_00281973_003b-1979_0029">Kowalski (1973; 1979)</a>, in
Edinburgh, recognized that execution of a Prolog program could be interpreted
as proving theorems (using a proof technique called linear Horn-clause
resolution).  The merging of the last two strands led to the logic-programming
movement.  Thus, in assigning credit for the development of logic programming,
the French can point to Prolog’s genesis at the University of Marseille, while
the British can highlight the work at the University of Edinburgh.  According
to people at <abbr>MIT</abbr>, logic programming was developed by these groups in
an attempt to figure out what Hewitt was talking about in his brilliant but
impenetrable Ph.D. thesis.  For a history of logic programming, see 
<a href="References.xhtml#Robinson-1983">Robinson 1983</a>.</p>
</div>
<div id="FOOT263"><p><a class="footnote_backlink" href="#DOCF263"><sup>263</sup></a>
To see the correspondence between the
rules and the procedure, let <code>x</code> in the procedure (where <code>x</code> is
nonempty) correspond to <code>(cons u v)</code> in the rule.  Then <code>z</code> in the
rule corresponds to the <code>append</code> of <code>(cdr x)</code> and <code>y</code>.</p>
</div>
<div id="FOOT264"><p><a class="footnote_backlink" href="#DOCF264"><sup>264</sup></a>
This certainly does not relieve the user of the entire
problem of how to compute the answer.  There are many different mathematically
equivalent sets of rules for formulating the <code>append</code> relation, only some
of which can be turned into effective devices for computing in any direction.
In addition, sometimes “what is” information gives no clue “how to” compute
an answer.  For example, consider the problem of computing the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math> such that
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msup>
      <mi>y</mi>
      <mn>2</mn>
    </msup>
    <mo>=</mo>
    <mi>x</mi>
  </mrow>
</math>.</p>
</div>
<div id="FOOT265"><p><a class="footnote_backlink" href="#DOCF265"><sup>265</sup></a>
Interest in logic programming peaked during the early 80s
when the Japanese government began an ambitious project aimed at building
superfast computers optimized to run logic programming languages.  The speed of
such computers was to be measured in LIPS (Logical Inferences Per Second)
rather than the usual FLOPS (FLoating-point Operations Per Second).  Although
the project succeeded in developing hardware and software as originally
planned, the international computer industry moved in a different direction.
See <a href="References.xhtml#Feigenbaum-and-Shrobe-1993">Feigenbaum and Shrobe 1993</a> for an overview evaluation of the Japanese
project.  The logic programming community has also moved on to consider
relational programming based on techniques other than simple pattern matching,
such as the ability to deal with numerical constraints such as the ones
illustrated in the constraint-propagation system of <a href="3_002e3.xhtml#g_t3_002e3_002e5">3.3.5</a>.</p>
</div>
<div id="FOOT266"><p><a class="footnote_backlink" href="#DOCF266"><sup>266</sup></a>
This uses the dotted-tail notation
introduced in <a href="2_002e2.xhtml#Exercise-2_002e20">Exercise 2.20</a>.</p>
</div>
<div id="FOOT267"><p><a class="footnote_backlink" href="#DOCF267"><sup>267</sup></a>
Actually, this description of <code>not</code> is valid
only for simple cases.  The real behavior of <code>not</code> is more complex.  We
will examine <code>not</code>’s peculiarities in <a href="#g_t4_002e4_002e2">4.4.2</a> and
<a href="#g_t4_002e4_002e3">4.4.3</a>.</p>
</div>
<div id="FOOT268"><p><a class="footnote_backlink" href="#DOCF268"><sup>268</sup></a>
<code>Lisp-value</code> should be used
only to perform an operation not provided in the query language.  In
particular, it should not be used to test equality (since that is what the
matching in the query language is designed to do) or inequality (since that can
be done with the <code>same</code> rule shown below).</p>
</div>
<div id="FOOT269"><p><a class="footnote_backlink" href="#DOCF269"><sup>269</sup></a>
Notice that we do not need <code>same</code> in order to make two
things be the same: We just use the same pattern variable for each—in effect,
we have one thing instead of two things in the first place.  For example, see
<code>?town</code> in the <code>lives-near</code> rule and <code>?middle-manager</code> in the
<code>wheel</code> rule below.  <code>Same</code> is useful when we want to force two
things to be different, such as <code>?person-1</code> and <code>?person-2</code> in the
<code>lives-near</code> rule.  Although using the same pattern variable in two parts
of a query forces the same value to appear in both places, using different
pattern variables does not force different values to appear.  (The values
assigned to different pattern variables may be the same or different.)</p>
</div>
<div id="FOOT270"><p><a class="footnote_backlink" href="#DOCF270"><sup>270</sup></a>
We will also allow rules without bodies, as in <code>same</code>, and
we will interpret such a rule to mean that the rule conclusion is satisfied by
any values of the variables.</p>
</div>
<div id="FOOT271"><p><a class="footnote_backlink" href="#DOCF271"><sup>271</sup></a>
Because matching is generally very expensive, we would like
to avoid applying the full matcher to every element of the data base.  This is
usually arranged by breaking up the process into a fast, coarse match and the
final match.  The coarse match filters the data base to produce a small set of
candidates for the final match.  With care, we can arrange our data base so
that some of the work of coarse matching can be done when the data base is
constructed rather then when we want to select the candidates.  This is called
<a id="index-indexing"></a>
<em>indexing</em> the data base.  There is a vast technology built around
data-base-indexing schemes.  Our implementation, described in 
<a href="#g_t4_002e4_002e4">4.4.4</a>, contains a simple-minded form of such an optimization.</p>
</div>
<div id="FOOT272"><p><a class="footnote_backlink" href="#DOCF272"><sup>272</sup></a>
But this kind of exponential
explosion is not common in <code>and</code> queries because the added conditions tend
to reduce rather than expand the number of frames produced.</p>
</div>
<div id="FOOT273"><p><a class="footnote_backlink" href="#DOCF273"><sup>273</sup></a>
There is a large literature on
data-base-management systems that is concerned with how to handle complex
queries efficiently.</p>
</div>
<div id="FOOT274"><p><a class="footnote_backlink" href="#DOCF274"><sup>274</sup></a>
There is a subtle difference between this
filter implementation of <code>not</code> and the usual meaning of <code>not</code> in
mathematical logic.  See <a href="#g_t4_002e4_002e3">4.4.3</a>.</p>
</div>
<div id="FOOT275"><p><a class="footnote_backlink" href="#DOCF275"><sup>275</sup></a>
In one-sided pattern matching, all the
equations that contain pattern variables are explicit and already solved for
the unknown (the pattern variable).</p>
</div>
<div id="FOOT276"><p><a class="footnote_backlink" href="#DOCF276"><sup>276</sup></a>
Another way to think of unification is that
it generates the most general pattern that is a specialization of the two input
patterns.  That is, the unification of <code>(?x a)</code> and <code>((b ?y) ?z)</code> is
<code>((b ?y) a)</code>, and the unification of <code>(?x a ?y)</code> and <code>(?y ?z
a)</code>, discussed above, is <code>(a a a)</code>.  For our implementation, it is more
convenient to think of the result of unification as a frame rather than a
pattern.</p>
</div>
<div id="FOOT277"><p><a class="footnote_backlink" href="#DOCF277"><sup>277</sup></a>
Since unification is a generalization of matching, we could
simplify the system by using the unifier to produce both streams.  Treating the
easy case with the simple matcher, however, illustrates how matching (as
opposed to full-blown unification) can be useful in its own right.</p>
</div>
<div id="FOOT278"><p><a class="footnote_backlink" href="#DOCF278"><sup>278</sup></a>
The reason we use streams (rather than lists) of frames is
that the recursive application of rules can generate infinite numbers of values
that satisfy a query.  The delayed evaluation embodied in streams is crucial
here: The system will print responses one by one as they are generated,
regardless of whether there are a finite or infinite number of responses.</p>
</div>
<div id="FOOT279"><p><a class="footnote_backlink" href="#DOCF279"><sup>279</sup></a>
That a particular method of inference
is legitimate is not a trivial assertion.  One must prove that if one starts
with true premises, only true conclusions can be derived.  The method of
inference represented by rule applications is <a id="index-modus-ponens"></a>
<em>modus ponens</em>, the
familiar method of inference that says that if <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>A</mi>
</math> is true and <em>A
implies B</em> is true, then we may conclude that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>B</mi>
</math> is true.</p>
</div>
<div id="FOOT280"><p><a class="footnote_backlink" href="#DOCF280"><sup>280</sup></a>
We
must qualify this statement by agreeing that, in speaking of the “inference”
accomplished by a logic program, we assume that the computation terminates.
Unfortunately, even this qualified statement is false for our implementation of
the query language (and also false for programs in Prolog and most other
current logic programming languages) because of our use of <code>not</code> and
<code>lisp-value</code>.  As we will describe below, the <code>not</code> implemented in
the query language is not always consistent with the <code>not</code> of mathematical
logic, and <code>lisp-value</code> introduces additional complications.  We could
implement a language consistent with mathematical logic by simply removing
<code>not</code> and <code>lisp-value</code> from the language and agreeing to write
programs using only simple queries, <code>and</code>, and <code>or</code>.  However, this
would greatly restrict the expressive power of the language.  One of the major
concerns of research in logic programming is to find ways to achieve more
consistency with mathematical logic without unduly sacrificing expressive
power.</p>
</div>
<div id="FOOT281"><p><a class="footnote_backlink" href="#DOCF281"><sup>281</sup></a>
This is not a problem of the logic but one of the procedural
interpretation of the logic provided by our interpreter.  We could write an
interpreter that would not fall into a loop here.  For example, we could
enumerate all the proofs derivable from our assertions and our rules in a
breadth-first rather than a depth-first order.  However, such a system makes it
more difficult to take advantage of the order of deductions in our programs.
One attempt to build sophisticated control into such a program is described in
<a href="References.xhtml#deKleer-et-al_002e-1977">deKleer et al. 1977</a>.  Another technique, which does not lead to such serious
control problems, is to put in special knowledge, such as detectors for
particular kinds of loops (<a href="#Exercise-4_002e67">Exercise 4.67</a>).  However, there can be no
general scheme for reliably preventing a system from going down infinite paths
in performing deductions.  Imagine a diabolical rule of the form “To show
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>P</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> is true, show that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>P</mi>
    <mo stretchy="false">(</mo>
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo stretchy="false">)</mo>
    <mo stretchy="false">)</mo>
  </mrow>
</math> is true,” for some
suitably chosen function <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math>.</p>
</div>
<div id="FOOT282"><p><a class="footnote_backlink" href="#DOCF282"><sup>282</sup></a>
Consider the query
<code>(not (baseball-fan (Bitdiddle Ben)))</code>.  The system finds that
<code>(baseball-fan (Bitdiddle Ben))</code> is not in the data base, so the empty
frame does not satisfy the pattern and is not filtered out of the initial
stream of frames.  The result of the query is thus the empty frame, which is
used to instantiate the input query to produce <code>(not (baseball-fan
(Bitdiddle Ben)))</code>.</p>
</div>
<div id="FOOT283"><p><a class="footnote_backlink" href="#DOCF283"><sup>283</sup></a>
A discussion
and justification of this treatment of <code>not</code> can be found in the article
by <a href="References.xhtml#Clark-_00281978_0029">Clark (1978)</a>.</p>
</div>
<div id="FOOT284"><p><a class="footnote_backlink" href="#DOCF284"><sup>284</sup></a>
In general, unifying <code>?y</code> with an
expression involving <code>?y</code> would require our being able to find a fixed
point of the equation <code>?y</code> = <code>⟨</code><var>expression involving <code>?y</code></var><code>⟩</code>.  It
is sometimes possible to syntactically form an expression that appears to be
the solution.  For example, <code>?y</code> = <code>(f ?y)</code> seems to have the fixed
point <code>(f (f (f <span class="roman">…</span> )))</code>, which we can produce by beginning with the
expression <code>(f ?y)</code> and repeatedly substituting <code>(f ?y)</code> for
<code>?y</code>.  Unfortunately, not every such equation has a meaningful fixed
point.  The issues that arise here are similar to the issues of manipulating
infinite series in mathematics.  For example, we know that 2 is the solution to
the equation <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>y</mi>
    <mo>=</mo>
    <mn>1</mn>
    <mo>+</mo>
    <mi>y</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mn>2</mn>
  </mrow>
</math>.  Beginning with the expression <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>1</mn>
    <mo>+</mo>
    <mi>y</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mn>2</mn>
  </mrow>
</math>
and repeatedly substituting <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>1</mn>
    <mo>+</mo>
    <mi>y</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mn>2</mn>
  </mrow>
</math> for <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math> gives
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mn>2</mn>
  <mo>=</mo>
  <mi>y</mi>
  <mo>=</mo>
  <mn>1</mn>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mfrac>
      <mi>y</mi>
      <mn>2</mn>
    </mfrac>
  </mrow>
  <mo>=</mo>
  <mn>1</mn>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mrow class="MJX-TeXAtom-ORD">
      <mfrac>
        <mn>1</mn>
        <mn>2</mn>
      </mfrac>
    </mrow>
    <mrow>
      <mo>(</mo>
      <mn>1</mn>
      <mo>+</mo>
      <mrow class="MJX-TeXAtom-ORD">
        <mfrac>
          <mi>y</mi>
          <mn>2</mn>
        </mfrac>
      </mrow>
      <mo>)</mo>
    </mrow>
  </mrow>
  <mo>=</mo>
  <mn>1</mn>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mfrac>
      <mn>1</mn>
      <mn>2</mn>
    </mfrac>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mfrac>
      <mi>y</mi>
      <mn>4</mn>
    </mfrac>
  </mrow>
  <mo>=</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mo>…<!-- … --></mo>
    <mo>,</mo>
  </mrow>
</math>
which leads to
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mn>2</mn>
  <mo>=</mo>
  <mn>1</mn>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mfrac>
      <mn>1</mn>
      <mn>2</mn>
    </mfrac>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mfrac>
      <mn>1</mn>
      <mn>4</mn>
    </mfrac>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mfrac>
      <mn>1</mn>
      <mn>8</mn>
    </mfrac>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mo>…<!-- … --></mo>
    <mo>.</mo>
  </mrow>
</math>
However, if we try the same manipulation beginning with the observation that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo>−</mo>
    <mn>1</mn>
  </mrow>
</math> 
is the solution to the equation <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>y</mi>
    <mo>=</mo>
    <mn>1</mn>
    <mo>+</mo>
    <mn>2</mn>
    <mi>y</mi>
  </mrow>
</math>, we obtain
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <mo>−<!-- − --></mo>
    <mn>1</mn>
  </mrow>
  <mo>=</mo>
  <mi>y</mi>
  <mo>=</mo>
  <mn>1</mn>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mn>2</mn>
    <mi>y</mi>
  </mrow>
  <mo>=</mo>
  <mn>1</mn>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mn>2</mn>
    <mo stretchy="false">(</mo>
    <mn>1</mn>
    <mo>+</mo>
    <mn>2</mn>
    <mi>y</mi>
    <mo stretchy="false">)</mo>
  </mrow>
  <mo>=</mo>
  <mn>1</mn>
  <mo>+</mo>
  <mn>2</mn>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mn>4</mn>
    <mi>y</mi>
  </mrow>
  <mo>=</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mo>…<!-- … --></mo>
    <mo>,</mo>
  </mrow>
</math>
which leads to
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mo>−<!-- − --></mo>
  <mn>1</mn>
  <mo>=</mo>
  <mn>1</mn>
  <mo>+</mo>
  <mn>2</mn>
  <mo>+</mo>
  <mn>4</mn>
  <mo>+</mo>
  <mn>8</mn>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mo>…<!-- … --></mo>
    <mo>.</mo>
  </mrow>
</math>
Although the formal manipulations used in deriving these two equations are
identical, the first result is a valid assertion about infinite series but the
second is not.  Similarly, for our unification results, reasoning with an
arbitrary syntactically constructed expression may lead to errors.</p>
</div>
<div id="FOOT285"><p><a class="footnote_backlink" href="#DOCF285"><sup>285</sup></a>
Most Lisp systems give the user the ability to modify the
ordinary <code>read</code> procedure to perform such transformations by defining
<a id="index-reader-macro-characters"></a>
<em>reader macro characters</em>.  Quoted expressions are already handled in
this way: The reader automatically translates <code>'expression</code> into
<code>(quote expression)</code> before the evaluator sees it.  We could arrange for
<code>?expression</code> to be transformed into <code>(? expression)</code> in the same
way; however, for the sake of clarity we have included the transformation
procedure here explicitly.
</p>
<p><code>Expand-question-mark</code> and <code>contract-question-mark</code> use several
procedures with <code>string</code> in their names.  These are Scheme primitives.</p>
</div>
</div>
<nav class="header">
<p>
Next: <a href="Chapter-5.xhtml#Chapter-5" accesskey="n" rel="next">Chapter 5</a>, Prev: <a href="4_002e3.xhtml#g_t4_002e3" accesskey="p" rel="prev">4.3</a>, Up: <a href="#g_t4_002e4_002e4" accesskey="u" rel="prev">4.4.4</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>


</section><span class="bottom jump" title="Jump to bottom"><a href="#pagebottom" accesskey="b">⇣</a></span><a id="pagebottom"></a>
</body>
</html>